3678154_ac_313ms_1348k.cpp

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

#include <stdio.h>

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

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

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;
			int l1, l2;
			if (com[0] == 'D')
			{
				l1 = l2 = 0;
				u = findset(a, l1);
				v = findset(b, l2);
				if (u != v)
				{
						if (rank[u] > rank[v])
						{
							p[v] = u;
							len[v] = (l1 + l2 + 1) % 2;
						}
						else
						{
							p[u] = v;
							len[u] = (l1 + l2 + 1) % 2;
							if (rank[u] == rank[v])
							{
								rank[v]++;
							}
						}
				}
				continue;
			}
			l1 = l2 = 0;
			u = findset(a, l1);
			v = findset(b, l2);
			if (u != v)
			{
				puts("Not sure yet.");
				continue;
			}
			if ((l1 + l2) % 2 == 0)
				puts("In the same gang.");
			else
				puts("In different gangs.");
		}
	}
	return 0;
}