LA 3644 易爆物 并查集

题目链接：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1645

题意：有一些化合物，每种化合物中含有两种元素，如果有k种化合物含有K种元素就会爆炸，现在装车司机按照输入顺序一件一件的装，遇到加入后会爆炸的化合物就不装，问会有多少化合物不能被装入。

解法：将每种元素看成一个顶点，一个化合物含有两种元素就是一条边，构图完成后，出现环就意味着爆炸，所以用并查集，像Kruskal算法一样为同一连通分量的为同一个父节点，加入某种化合物，该化合物的两种元素已经连通，如果再加进来就会出现环。。。拒绝该化合物进入。

贴代码：

#include<cstdio>
#include<cstring>
const int N=100005;
int pa[N];
int findset(int x)
{
    return pa[x] == -1 ?x:x=findset(pa[x]);
}
int main()
{
//    freopen("in.txt","r",stdin);
    int cnt,x,y;
    while(scanf("%d",&x) == 1)
    {
        cnt =0;
        memset(pa,-1,sizeof(pa));
        while(x != -1)
        {
            scanf("%d",&y);
            x = findset(x) ;
            y = findset(y);
            if(x==y ) ++cnt;
            else pa[x]=y;
            scanf("%d",&x);
        }
        printf("%d
",cnt);
    }
    return 0;
}