UVALive 3644 - X-Plosives（帶環并查集）

題目大意：

給出一些化合物，每組化合物由兩個元素組成，在N>2的情況下，如果有n組化合物正好對應n種物質，如：A - B B - C C - A 這樣就會産生爆炸，就不餓能要了，對于每組化合物，如果會産生爆炸則不能要，否則必須要。

解題思路：

經典帶環并查集。看了一晚上硬是沒看出來，題解把每一組化合物看成一個邊，把每一個元素看成點，進來一組就連一組，如果成環的話則ans++，最後輸出ans即可。AC代碼：

PS：多組輸入是個坑，注意一下

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int _max = 1e5+50;
int f[_max],ans=0,a,b;
int find(int x)//尋根+路徑壓縮
{
	return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y)//判斷是否合并
{
	int t1=find(x);
	int t2=find(y);
	t1==t2?ans++:f[t2]=t1;
}
void init()
{
	ans=0;
	for(int i=0;i<_max;i++)
	  f[i]=i;
}
int main()
{
	for(int i=0;i<_max;i++)
	  f[i]=i;
	while(cin>>a)
	{
		if(a==-1)
		{
			cout<<ans<<endl;
			init();
			continue;
		}
		cin>>b;
		merge(a,b);
	}
	//system("pause");
	return 0;
}