UVALive 3644 X-Plosives(簡單并查集)

題目大意：

把一些兩個元素組成的化合物按輸入次序往車上裝，如果會發生爆炸(存在k個簡單化合物，正好包含k種元素)，記錄，輸出不能裝車的化合物總數。

做法：由于是其中K各簡單化合物中包含K個元素，仔細一想就是并查集，把已經出現的點合成一個集合，對于新出現的兩個值，如果兩個值同時在一個集合中（注意可能不止一個集合），那麼在這個集合中就肯定能找到另外幾對數值使得他們與這一對數值構成一個環，如現在的為A+B；因為A，B已經在集合中了，是以集合中必然有(A,C),(X,B).而C和X都在集合中，就可以找到一條路徑連接配接C,X；于是在這條路上的所有點就構成了 ( 存在k個簡單化合物，正好包含k種元素 )。 代碼如下：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx=100050;
int father[maxx];
int findfather(int x)
{
    return father[x]==x?x:findfather(father[x]);
}

void init(){
for(int i=0;i<maxx;i++)
father[i]=i;
}

int main(){
int a,b;int flag=0;
init();
while(cin>>a)
{
    if(a==-1){//注意是多組資料
        cout<<flag<<endl;
flag=0;
init();
        continue;
    }
    cin>>b;
int aa=findfather(a);
int bb=findfather(b);
if(aa==bb)flag++;
else father[aa]=bb;
}
return 0;}