原题链接Online JudgeOnline Judgehttps://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3601
VJ链接X-Plosives - UVA 1160 - Virtual Judgehttps://vjudge.net/problem/UVA-1160
题目描述:给你几组数a和b，表示a和b会形成化合物，如果有有超过3个物品互相形成化合物就会爆炸。这样的物品不能装上车，如果让你按照给出的顺序把这些物品装上车，有多少组不能够装上车？ 输入格式：每行两个数，表示每个化合物的两个元素。以-1结束。 输出格式：不能装上车的化合物数量。
样例解读
简单的画一下图,可以发现
如果a,b成环,就是不能装上车的化合物
从图中来看,如果a,b有共同的连接点,再出现a b的化合物,那么就会成环,也就是不能装上车
我们可以用树来存储这一特性,只需检查a b是否有相同的根节点.
可以把最开始出现的元素作为根节点,后面与它化合的元素作为子节点
如果前面没出现过这个元素,就把它作为根节点,生成一颗新树.
简言之,在同一颗树上的元素不能再与树上的其他结点形成化合物.
(You may assume that no repeated binding pairs appears in the input.
题目中已经假定不会重复出现相同的化合物)
进一步,我们只需记录某一元素与根节点的关系,而不需要记录这个元素与其他子节点的关系
也就是只需把有相同根节点的元素归为一个集合.如果输入的a b在同一个集合当中,就是我们要找的a b
采用并查集可以很好地解决这一问题.
此处find函数用于寻找元素x的根节点,并自带路径压缩.返回元素x的根节点
int find(int x)
{if(p[x]!=x) return p[x]=find(p[x]);return x;
}完整代码
#include<stdio.h>
#include<iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int x)
{if(p[x]!=x) return p[x]=find(p[x]);return x;
}
int main()
{int a,b;for(int i=1;i<=N;i++){p[i]=i;}int sum=0;while(scanf("%d",&a)!=EOF){if(a==-1){printf("%d\n",sum);for(int i=1;i<=N;i++){p[i]=i;} sum=0;continue;}scanf("%d",&b);if(find(a)==find(b)){sum++;}else{p[find(a)]=find(b);}}return 0;
}