当前位置: 代码迷 >> 综合 >> 并查集习题X-Plosives(uvaOJ1160)
  详细解决方案

并查集习题X-Plosives(uvaOJ1160)

热度:2   发布时间:2023-10-21 04:51:53.0

原题链接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结束。 输出格式:不能装上车的化合物数量。

样例解读

简单的画一下图,可以发现

并查集习题X-Plosives(uvaOJ1160)

如果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;
}