本文主要是介绍数据结构 B 爱攀比的童鞋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
B 爱攀比的童鞋
众所周知，中国人办事总是要讲点关系，中国人的人际关系一般都相当复杂。比如说你想混ACM就最好和miaowu姐姐攀上亲戚。。。ORZ。。。既然亲戚多了好办事，我们就要构筑一个亲戚网。假如你和xuanflyer是亲戚，xuanflyer和miaowu是亲戚，以后你有什么事也可以通过xuanflyer来找miaowu了，这样一来，你和miaowu也算亲戚了。跟wuyu姐姐一样，很多童鞋比较爱慕虚荣，喜欢攀比，所以总想知道他和他亲戚里面到底谁的钱最多。
输入：对每个样例，第一行：正整数n m q(1<=n,m,q<=100000)，表示有n个人，然后m行，每行输入i j，表示i和j是亲戚，然后q行，每行输入i，表示询问i和i的亲戚里面谁的钱最多。
PS：用1—n表示这n个人，第i个人有i万元。
输出：对每个询问，输出一行，输出i和i的亲戚里面谁的钱最多。
样例输入：
5 4 3
1 2
3 4
1 5
2 5
1
2
3
样例输出：
5
5
4
简单的并查集，直接套用模板，就是中间进行亲戚的钱的比较就行。
#include <stdio.h>
int pre[100010];
int find(int x)
{int r=x;while(pre[r]!=r)r=pre[r];return r;
}
int main()
{int i,n,m,p,p1,p2,f1,f2,t;scanf("%d%d%d",&n,&m,&p);for(i=1;i<=n;i++)pre[i]=i;while(m--){scanf("%d%d",&p1,&p2);f1=find(p1);f2=find(p2);if(f1!=f2){if(f1>f2)pre[f2]=f1;elsepre[f1]=f2;}}while(p--){scanf("%d",&t);printf("%d\n",find(t));}return 0;
}
这篇关于数据结构 B 爱攀比的童鞋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
