ACM全国邀请赛热身赛题2并查集

真是糟糕的一天，愿不要影响到明天邀请赛发挥。

题意：

有n个人。m次询问。每次询问包含两个数x和y，代表第x人和和第y人中有一个人是叛徒，一个不是叛徒。如果遇到第i次询问和之前询问出现冲突，则该询问为谎言。如果m条询问没有谎言，则输出1，和最大可能叛徒数，否则输出-1，遇到第几条时判断是谎言。

例：

输入

3 3

1 2

2 3

3 1

输出

-1 3

输入

5 4

1 2

2 3

3 4

4 1

输出

1 3

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXX = 100010;
int fa[MAXX], r[MAXX];
int vis[MAXX];
int find(int x){
	if (fa[x] == x) return fa[x];
	int tmp = fa[x];
	fa[x] = find(fa[x]);
	r[x] = (r[tmp] + r[x]) % 2;
	return fa[x];
}
void fun(int x, int y){
	int fx = find(x), fy = find(y);
	if (fx == fy)   return;
	fa[fy] = fx;
	r[fy] = (r[x] + 1 - r[y]) % 2;
}
int main(){
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int N, M, x, y, flag = 0, cnt = 0;
		scanf("%d%d", &N, &M);
		memset(vis, 0, sizeof(vis));
		for (int i = 0; i <= N; i++)   fa[i] = i, r[i] = 0;
		for (int i = 1; i <= M; i++) {
			scanf("%d%d", &x, &y);
			if (!vis[x])
				cnt++;
			if (!vis[y])
				cnt++;
			vis[x] = vis[y] = 1;
			if (flag)
				continue;
			if (find(x) == find(y)) {
				if (r[x] == r[y])
					flag = i;
			}
			else
				fun(x, y);
		}
		if (flag)
			printf("-1 %d\n", flag);
		else {
			int cnt2 = 0;
			for (int i = 1; i <= N; i++) {
				find(i);
				if (r[i] == 1 || !vis[i])
					cnt2++;
			}
			printf("1 %d\n", cnt - cnt2 > cnt2 ? cnt - cnt2 : cnt2);
		}
	}
	return 0;
}