Timus: Graph

1106.cpp

// ACM Timus 1106: Two Teams
// Source: http://acm.timus.ru/problem.aspx?space=1&num=1106
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

constexpr int MAXN = 1e2;
vector<int> adj[MAXN];
bool visited[MAXN];

int main(void)
{
    int n;
    cin >> n;

    // construction:
    for (int u = 0; u < n; u++)
    {
        int v;
        while (cin >> v && v)
            adj[u].push_back(v - 1);
    }

    // bfs:
    queue<int> q;
    vector<int> team(n);

    auto bfs = [&](int start) {
        int s = start;
        q.push(s);
        visited[s] = true;

        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto v : adj[u])
            {
                if (visited[v])
                    continue;
                visited[v] = true;
                q.push(v);
                team[v] = 1 ^ team[u];
            }
        }
    };

    for (int start = 0; start < n; start++)
        if (!visited[start])
            bfs(start);

    // Output:
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans += team[i];

    cout << ans << "\n";
    for (int i = 0; i < n; i++)
        if (team[i])
            cout << i + 1 << " ";

    cout << "\n";
}