题意:训练指南P191

分析:本题特殊,n个物品,n种元素则会爆炸,可以转移到图论里的n个点,连一条边表示u,v元素放在一起,如果不出现环,一定是n点,n-1条边,所以如果两个元素在同一个集合就会爆炸.

#include 
     
      using namespace std;const int N = 1e5 + 5;struct DSU	{	int rt[N], rk[N];	void init(void)	{		memset (rt, -1, sizeof (rt));		memset (rk, 0, sizeof (rk));	}	int Find(int x)	{		return rt[x] == -1 ? x : rt[x] = Find (rt[x]);	}	void Union(int x, int y)	{		x = Find (x);	y = Find (y);		if (x == y)	return ;		if (rk[x] > rk[y])	{			rt[y] = x;	rk[x] += rk[y] + 1;		}		else	{			rt[x] = y;	rk[y] += rk[x] + 1;		}	}	bool same(int x, int y)	{		return Find (x) == Find (y);	}}dsu;int main(void)	{	dsu.init ();	int ans = 0, x, y;	while (scanf ("%d", &x) == 1)	{		if (x == -1)	{			printf ("%d\n", ans);			dsu.init ();	ans = 0;			continue;		}		scanf ("%d", &y);		if (dsu.same (x, y))	ans++;		else	dsu.Union (x, y);	}	return 0;}