pku1703.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 76 行

#include <stdio.h>
#define TheMax 100010
int p[TheMax];
int s[TheMax];
int m, n;

void init()
{
	int i;
	for (i = 0; i <= n; i++)
	{
		p[i] = i;
		s[i] = 1;
	}
}

int Get_ID(int x)
{
	int root;
	if (x == p[x])
	{
		return x;
	}
	root = Get_ID(p[x]);
	s[x] = (s[x] + s[p[x]] + 1) % 2;
	p[x] = root;
	return root;
}

void Insert(int a, int b)
{
	int rb;
	rb = Get_ID(b);
	p[rb] = Get_ID(a);
	s[rb] = (s[a] + s[b]) % 2;
}

int main()
{
	char ch[3];
	int a, b, T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &n, &m);
		init();
		while (m--)
		{
			scanf("%s %d %d", ch, &a, &b);

			if (ch[0] == 'D')
			{
				Insert(a, b);
			}
			else
			{
				if (Get_ID(a) == Get_ID(b))
				{
					if (s[a] == s[b])
					{
						printf("In the same gang.\n");
					}
					else
					{
						printf("In different gangs.\n");
					}
				}
				else
				{
					printf("Not sure yet.\n");
				}
			}
		}
	}
	return 0;
}