3676797_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int m, n;
int len[100001], p[100001], rank[100001];

inline int findset(int x)
{
	if (x != p[x])
	{
		int t = p[x];
		p[x] = findset(t);
		len[x] += len[t];
		return p[x];
	}
	else
		return x;
}

void link(int x, int y)
{
	if (rank[x] > rank[y])
	{
		p[y] = x;
		len[y] = 1;
	}
	else
	{
		p[x] = y;
		len[x] = 1;
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
	}
}

int main()
{
	int T, a, b;
	char com[2];

	scanf("%d", &T);
	while (T-- != 0)
	{
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
		{
			len[i] = 0;
			p[i] = i;
			rank[i] = 0;
		}
		while (m-- != 0)
		{
			scanf("%s%d%d", com, &a, &b);
			int u, v;
			if (com[0] == 'D')
			{
				u = findset(a);
				v = findset(b);
				link(u, v);
				continue;
			}
			findset(a);
			findset(b);
			if (p[a] != p[b])
			{
				puts("Not sure yet.");
				continue;
			}
			if ((len[a] + len[b]) % 2 == 0)
				puts("In the same gang.");
			else
				puts("In different gangs.");
		}
	}
	return 0;
}