部分内容摘自博客http://blog.csdn.net/u012881011/article/details/46883863，感谢
| 易爆物D305 |
| 运行时间限制：1000ms； 运行空间限制：51200KB； |
|
试题描述
|
|
有一些简单化合物，每个化合物部由两种元素组成的（每个元素用一个大写字母表示）。你是一个装箱工人，从实验员那里按照顺序依次把一些简单化合物装到车上。但这里存在一个安全隐患：如果车上存在k个简单化合物，正好包含k种元素，那么它们将组成一个易爆的混合物。为了安全起见，每当你拿到一个化合物时，如果它和已装车的化合物形成易爆混合物，你就应当拒绝装车；否则就应该装车。编程输出有多少个没有装车的化合物。 |
|
输入
|
|
第一行包含一个正整数n，表示化合物的个数。接下来有n行，每行包括两个不同的整数a和b，表示一个由元素a和元素b组成的简单化合物。所有简单化合物按照交给你的先后顺序排列。
|
|
输出
|
|
一个数，表示没有装车的化合物的个数。
|
|
输入示例
|
|
6 2 4 3 4 2 9 3 8 4 8 3 9
|
|
输出示例
|
|
2
|
|
其他说明
|
|
数据范围：0 <= a，b <= 10^5，提示：并查集的相关知识。 样例说明：化合物4 8和化合物3 9没有装车。
|
题解：
可以用并查集来做。每一种元素看成一个独立的顶点，则一个化合物就是一条边。若两个元素联通，则危险不装车，ans++；否则就装车。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[],b[],f[],ans,cnt;
int gets(int x1)
{
if(f[x1]==x1) return x1;
f[x1]=gets(f[x1]);
return f[x1];
} void h(int x,int y)
{
int f1=gets(x),f2=gets(y);
if(f1==f2)
ans++;
else
f[f1]=f2;
} int main()
{
int i,u=,k=;
scanf("%d",&n);
for(i=;i<=;i++) f[i]=i;
for(i=;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(i=;i<=n;i++)
{
h(a[i],b[i]);
}
printf("%d",ans); return ;
}
D305