Google bi-coloring.

5
2 0
1 3 0
2 0
5 0
4 0

I've been struggling hard to overcome WA 8...
Then I've made these test cases and got AC in one go.
I hope these tests will be helpful to overcome WA... :)

Case 1:
4
3 0
4 0
1 0
2 0
Ans:
2
1 2

Case 2:
2
2 0
1 0
Ans:
1
1

Case 3:
3
2 3 0
1 3 0
1 2 0
Ans:
1
1

Case 4:
3
2 0
1 3 0
2 0
Ans:
2
1 3

Case 5:
4
2 4 0
1 0
4 0
1 3 0
Ans:
2
1 3

Case 6:
5
5 0
5 0
5 0
5 0
1 2 3 4 0
Ans:
4
1 2 3 4

Case 7:
5
2 0
1 0
5 0
5 0
3 4 0
Ans:
3
1 3 4

Let me know if any1 finds any error...
Thanks.

Edited by author 20.06.2016 22:19

write 7 test. Please.

There cannot be any impossible case as is suggested by the very first line of the problem statement

I recommend you this resource: https://e-maxx.ru/algo/bfs
also you can make a function instead of the lyambda, but I just like lyambdas more.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector <vector <int>> g(N);
    int h;
    for (int i = 0; i < N; i++) {
        for (;;) {
            cin >> h;
            if (!h)
                break;
            g[i].push_back(h - 1);
        }
    }
    int n = g.size();
    queue<int> q;
    vector<bool> used(n);
    vector<int> d(n);
    int s;
    auto bfs = [&](int start) {
        s = start;
        q.push(s);
        used[s] = true;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (size_t i = 0; i<g[v].size(); ++i) {
                int to = g[v][i];
                if (!used[to]) {
                    used[to] = true;
                    q.push(to);
                    d[to] = d[v] + 1;
                }
            }
        }
    };
    for (int start = 0; start < n; ++start)
        if (!used[start]) {
            bfs(start);
        }
    vector <int> ans;
    for (int i = 0; i < n; i++) {
        if (d[i] % 2 == 0)
            ans.push_back(i + 1);
    }
    int size = ans.size();
    cout << size << '\n';
    for (int i = 0; i < size; i++)
        cout << ans[i] << " ";
}

Edited by author 26.01.2019 22:53

Edited by author 30.01.2019 03:16

My solution is crushed on 11 test.
please help me...

//problem solved (issue of different compilers of my local PC and judge one)

Edited by author 26.03.2017 16:41

how can i see my current accepted submission rank????

what's wrong with this code:
#include <iostream>
#include <vector>
#include <list>
using namespace std;

int ar[102][102],viz[102];
int n;
list <int> a;
int dfs(int s)
{
    viz[s] = 1;
    for (int i=1;i<=n;i++)
    {

        if (ar[i][s] && !viz[i]) {dfs(i);  }//a.push_back(i);}
    }
    return 0;
}

int main()
{
    cin >> n;
    int z;
    for (int i=1;i<=n;)
    {
        cin >> z;
        if (z == 0) i++;
        else ar[i][z] = 1;
    }
    dfs(1);
    for (int i=1;i<=n;i++)
        if(!viz[i]) a.push_back(i);
    cout << a.size() << endl;
    for (int n : a) {
        cout << n << " ";
    }
    return 0;
}


maybe i didn't understand problem properly,some help?

1. Answer always exists.
2. Use DFS for all unmarked vertices and mark them: if current vertex is marked as x, all next must be marked as (x + 1) % 2. (0->1, 1->0)
3. Then just print all vertices marked by 0 (or 1).

my code is running correctly but yet it fails at test 1 :(

Earlier I had got a WA 9 but now I'm getting a WA 5 with the same code. What's the logic?

#include <iostream>
using namespace std;
long f[101],n;
int main()
  {
    long i,t,c=0;
    cin>>n;
    for (i=1;i<=n;i++)
      {
        if (f[i]==0) f[i]=1;
        while (true)
          {
            cin>>t;
            if (t==0) break;
            if (f[t]==0) f[t]=1+(f[i]==1);
          }
        if (f[i]==1) c++;
      }
    cout<<c<<endl;
    for (i=1;i<=n;i++)
        if (f[i]==1) cout<<i<<" ";
  }

why??

I am getting a wrong answer in it. Can anyone please help me?

Is there any better solution?

But established it with an error which makes me WA #13.
Guess cases before #13 are simple with no big number of vex.

WA 6
3
2 0
1 3 0
2 0
-----
2
1 3

3
2 3 0
1 0
1 0
--
1
1

WA 11
4
2 0
1 4 0
4 0
2 3 0
--
2
1 3

WA 13
3
3 0
3 0
1 2 0
--
2
1 2

Hi,

I have a solution which seems correct. For the first test it gives me the following answer:

4
1 4 5 6

I consider, it fits to the problem statement. Could anyone clarify, what is going wrong?

My algorithm is based on BFS and I always mark start vertex in a connected component as a first team vertex.