UVA 1160 X-Plosives
题意：
现在手上有一些化合物，每个化合物都不相同且由两个不同整数构成，当你手上存在这种情况时：
手上有至少N（N>2）个化合物且其中有N个化合物正好包含N个不同的整数（即这N个整数每个出现了2次）。那么此时化合物不稳定。比如你有化合物（1，2），（2，3）,（3，1）那么就是不稳定的，但是你如果只有（1，2）,（2，3） 那么就是稳定的。
现在给出所有化合物给你的顺序，你要保证不会出现化合物不稳定的情况，输出你需要拒绝化合物的个数。
输入：包含多组实例。每个实例由连续的一对整数构成（整数属于[0，10^5]）。不同实例之间是一个空行，没有重复的化合物会出现，且单行-1表示当前实例的输入结束。
输出：输出你需要拒绝的化合物个数。
分析：
把每个整数看成是节点，对应的化合物看成对应的边，那么就形成了一个无向图。
图中有环 充要条件 化合物不稳定。
我们添加某个化合物会不稳定 充要条件是 该化合物的两种元素已经属于同一个连通分量了。
判断化合物的两种元素已经在同一个连通分量时，直接拒绝即可。
本题需小心处理输入数据的输入格式。
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 500005
int pre[maxn];
int Find(int m)
{
int n=m;
while(n!=pre[n])
n=pre[n];
return n;
}
void Merge(int x,int y)
{
int fx=Find(x);
int fy=Find(y);
if(fx<fy)
pre[fy]=fx;//大的指向小的
else
pre[fx]=fy;
}
void init()
{
int i;
for(i=0;i<500005;i++)
pre[i]=i;
}
int main()
{
int x,y;
while(scanf("%d",&x)==1)
{
if(x==-1)//特例
{
printf("0\n");
continue;
}
int cnt=0;//需要拒绝的化合物数
init();
while(x!=-1)
{
scanf("%d",&y);
if(Find(x) == Find(y))
++cnt;
else
Merge(x,y);
scanf("%d",&x);
}
printf("%d\n",cnt);
}
return 0;
}