UVA1160题解

前置知识

• 并查集

简单的查找（带路经压缩）:

int find(int x){
	return x == fa[x] ? x : fa[x] = find(fa[x]);
    // fa[i] 为并查集的数组
}

查找（这里可以数据小完全不需要用启发式合并）：

void merge(int x,int y){
	int f = find(x),t = find(y);
    fa[f] = t;
}

查阅资料可知，只用路径压缩，不用启发式合并的平均时间复杂度为 \(\mathcal{O}(\alpha (n))\) ，最坏时间复杂度为 \(\mathcal{O}(m \log n)\) 。

思路

首先可以将每个元素看成点，化合物看成边，因为如果有超过 3 个物品互相形成化合物就会爆炸，所以会爆炸的条件可以看成两个是在同一祖先（在同一集合）中，（如果这两个点有一个祖先的话，合并就会有 3 个物品在一起的）。

每一次都将不在一个集合中两个数合并。

#include<cstdio>
#include<iostream>

using namespace std;

int fa[100010];

int find(int x){
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main()
{
	int x,y;
	while(scanf("%d",&x) == 1){    \\ 注意输入
		for(int i=1;i<=100010;i++)	fa[i] = i;
		int ans = 0;
		while(x != -1){
			scanf("%d",&y);
			int f = find(x),t = find(y);
			if(f == t)	ans ++;
			else
				fa[f] = t;    // 如果不会爆炸，就合并
			scanf("%d",&x);
		}
		cout<<ans<<endl;
	}
	return 0;
}