Is there anybody who can help me?

I think my algorithm is correct, but keeps get WA.

My algoirthm:

1. Process each connected components("CC") one by one

2. For each CC, if there is only one vertex belongs to it, then the answer is increased by 1. if there are more than one vertex belong to it, we check if it is a bipartite graph, if not, we assert that the problem is no solution. otherwise, we count the number of vertices in set X and set Y. obviously, we choose the smaller between them.

Here is my code.

Code: Select all

```
#include <cstdio>
#include <cstring>
const int limit_size = 200 + 10;
int n , m;
bool mat [ limit_size ][ limit_size ];
int cnt [ 2 ];
void init()
{
int i , a , b;
memset(mat , 0 , sizeof(mat));
scanf("%d%d" , &n , &m);
for(i = 0; i < m; i ++)
{
scanf("%d%d" , &a , &b);
mat[a][b] = mat[b][a] = 1;
}
}
bool mark [ limit_size ];
int color [ limit_size ];
int queue [ limit_size ];
int head , tail;
bool check()
{
int i , j;
for(i = 0; i <= tail; i ++)
for(j = i + 1; j <= tail; j ++)
if( mat[ queue[i] ][ queue[j] ] && color[ queue[i] ] == color[ queue[j] ] ) return 0;
return 1;
}
void solve()
{
int i , u , v;
int ret = 0;
memset(mark , 0 , sizeof(mark));
for(i = 0; i < n; i ++)
if(! mark[i])
{
cnt[0] = cnt[1] = 0;
queue[ head = tail = 0 ] = i;
mark[i] = 1; color[i] = 0; cnt[0] = 1;
while(head <= tail)
{
u = queue[ head ++ ];
for(v = 0; v < n; v ++)
if(mat[u][v] && ! mark[v])
{
queue[ ++ tail ] = v;
mark[v] = 1; color[v] = 1 - color[u]; cnt[ color[v] ] ++;
}
}
if(tail == 0)
{
ret ++; continue ;
}
if(! check())
{
printf("-1"); return ;
}
ret += cnt[0] <? cnt[1];
}
printf("%d\n" , ret);
}
int main()
{
int cnt_case;
for(scanf("%d" , &cnt_case); cnt_case --;)
{
init();
solve();
}
return 0;
}
```