易爆物（X-Plosives，LA 3644 ）

题目链接

https://vjudge.net/problem/UVALive-3644

题意

有一些化合物，每个化合物由两种元素组成。现要将这些化合物装车。但如果车上的化合物的子集满足化合物的个数等于元素的种类，那么就会爆炸。即每当你手里拿着一个化合物，你要考虑将这个化合物装车后是否会爆炸，如果会，你应该拒绝装车。求有多少个没有装车的化合物。

分析

将元素看作点，化合物看作边。如果形成了环，那么点的数量就和边的数量相等了。所以用并查集去判断在建图的过程中有没有形成环即可。

代码

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+100;
int par[maxn],ans;
void init()//并查集初始化
{for(int i=0;i<maxn;i++) par[i]=i;ans=0;
}
int find(int x)//查找根，路径压缩
{if(par[x]==x) return x;return par[x]=find(par[x]);
}
bool same(int x,int y)//判断是否在一个集合内
{return find(x)==find(y);
}
void unit(int x,int y)//合并
{int fx=find(x),fy=find(y);par[fx]=fy;
}int main()
{int a,b;init();while(cin>>a){if(a==-1){cout<<ans<<endl;init();continue;}cin>>b;if(!same(a,b)){unit(a,b);}else{ans++;}}return 0;
}