题目&＃xff1a;http://www.fjutacm.com/Problem.jsp?pid&＃61;2021
题意大概就是输入n&＃xff0c;m&＃xff0c;分别代表总共n个人&＃xff0c;m组&＃xff0c;每组输入k&＃xff0c;后面再输入k个人表示是一组的&＃xff0c;0号是嫌疑者&＃xff0c;输出和0在一组的人数(嫌疑者的人数)。
想看题目的点击这里哦&＃xff1a;--->题目
友情链接&＃xff1a;--->点我
咳咳&＃xff0c;下面就是代码分析阶段&＃xff0c;请看&＃xff1a;
#include
int fa[30005],n,rak[30005];
void chushihua()//初始化&＃xff0c;把每个人的父节点先设为自己。rak就是代表的人数(同一个集合的人数)
{for(int i&＃61;0;i
int find(int x)
{int r&＃61;x,temp;while(r!&＃61;fa[r])r&＃61;fa[r];while(x!&＃61;fa[x])//这里是路径压缩&＃xff0c;让这棵树扁平化&＃xff0c;把每个节点的父节点都直接变成根节点(让树变粗)。 {temp&＃61;fa[x];fa[x]&＃61;r;x&＃61;temp;}return x;
}
void hebing(int a,int b)//合并操作&＃xff0c;也有点小细节
{a&＃61;find(a);b&＃61;find(b);if(a!&＃61;b){fa[b]&＃61;a;rak[a]&＃43;&＃61;rak[b];//这里就把人数统计出来了&＃xff0c;注意这里的a&＃xff0c;b的位置。 }
}
int main(void)
{int m,k,a,b;//这里的a表示的是每一组第一个学生 &＃xff0c;b表示的就是后面的学生 while(scanf("%d%d",&n,&m)&&n)//&&n表示当n和m同时为0就退出&＃xff0c;但是不用写&&m&＃xff0c;至于为什么&＃xff0c;请读者自行领会 {chushihua();for(int i&＃61;0;i
小结一下&＃xff1a;这个题是我学习并查集做的第二个题&＃xff0c;比较基础适合并查集入门&＃xff0c;感觉特别能体现出并查集的能力&＃xff0c;如果没看懂题的话可能还是有点难度&＃xff0c;不过也是巧&＃xff0c;这道题讲的是有关病毒传染的&＃xff0c;而作者所处的时间正好也是病毒四处传播&＃xff0c;危害人民的时间&＃xff0c;话不多说&＃xff0c;武汉加油&＃xff01;
京公网安备 11010802041100号