Input:
Code: Select all
1
5
2 2 3
2 1 3
2 1 2
1 5
1 4
Code: Select all
1
Moderator: Board moderators
Code: Select all
1
5
2 2 3
2 1 3
2 1 2
1 5
1 4
Code: Select all
1
Code: Select all
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <utility>
using namespace std;
int N;
vector<int> G[201];
bool visited[201];
int color[201];
vector<int> answers;
int BFS(int root)
{
queue<int> Q;
visited[root] = true;
color[root] = 0;
Q.push(root);
bool isBipartite = true;
int totalSize = 0;
int black = 0;
while(!Q.empty())
{
int current = Q.front(); Q.pop();
if(color[current] == 1) ++black;
++totalSize;
for(int i = 0; i < G[current].size(); ++i)
{
int child = G[current][i];
if(!visited[child])
{
color[child] = 1 - color[current];
visited[child] = true;
Q.push(child);
}
else if(color[current] == color[child])
{
isBipartite = false;
}
}
}
//if(isBipartite) cout<<"IT IS\n";
////else cout<<"IT IS NOT\n";
if(isBipartite) return max(black, totalSize - black);
else return 0;
}
void read()
{
for(int i = 0; i < 201; ++i) G[i].clear();
memset(visited, 0, sizeof visited);
memset(color, -1, sizeof color);
//now do shit
cin >> N;
for(int i = 1; i <= N; ++i)
{
int p;
cin >> p;
for(int j = 0; j < p; ++j)
{
int enemy;
cin >> enemy;
G[i].push_back(enemy);
G[enemy].push_back(i);
}
//cout<<" left i: "<<i<<endl;
}
int result = 0;
for(int i = 1; i <= N; ++i)
{
if(!visited[i])
{
//cout<<"ROOT: "<<i<<endl;
result += BFS(i);
}
}
answers.push_back(result);
}
int main()
{
ios::sync_with_stdio(false);
int M;
cin >> M;
for(int i = 0; i < M; ++i)
{
read();
//cout<<"left case: "<<i<<endl;
}
//cout<<"Answers:\n";
for(int i = 0; i < M; ++i)
{
cout<<answers[i]<<'\n';
}
return 0;
}
Scarecrow wrote:some input sets are like this. be sure to handle these
outputCode: Select all
1 5 5 2 4 6 8 10 3 1 3 6 0 0 3 1 6 7
Code: Select all
3
Code: Select all
1
2 2 3
2 1 3
3 1 2
1 5
1 4
brianfry713 wrote: Input:AC output:Code: Select all
1 5 2 2 3 2 1 3 2 1 2 1 5 1 4
Code: Select all
1
Why is this the case though?brianfry713 wrote:No, the output should be 0 in that case.
Code: Select all
2
1
1 1
2
1 1
2 1
Code: Select all
0
0