ＺＯＪ1789The Suspects 用简单的并查集水了。。。看到有的题解用的是sum[ra] += sum[rb],这种叫什么名字，不记得了，但是这样肯定比我的好点。 #include <stdio.h>#include <iostream>#include <string>#include <cstring>using namespace std;int fa[30005]

并查集的同时记录这个集合里面的元素个数。用cnt来表示，初始时cnt[i] = 1;{ 0<= i <= n}.当合并的时候，假设x向y合并， 则需要cnt[y] += cnt[x] /************************************************ Author: fisty* Created Time: 2015/2/26 19:13:23* File N

带权表示集合总和。 代码： #include <stdio.h>#include <string.h>const int N = 30005;int parent[N], sum[N], n, m;int find(int x) {if (x == parent[x])return x;return parent[x] = find(parent[x]);}void init() {f

POJ 1611:The Suspects   Description 严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会, 最好的策略是隔离可能的患者。 在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。

题目链接 POJ-1611 题意 给定n学生，m小组，0号学生是病人，一组中只要有一个病人全部得病，求病人人数 思路 并查集模版，把每个组的学生分别连在一起，最后遍历全部节点即可。 代码 #include<iostream> #include<cmath>#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

这两道题非常相似，都是计算一个联通中所有节点的个数，只需要在find中加个计算就可以了 #include<stdio.h>int parent[10000005];int num[10000005];int find(int x){if(x != parent[x])parent[x] = find(parent[x]);return parent[x];}void Merge(i

今天讲的新东西是并查集啦~因为以前看过一个特别好理解的介绍并查集的文章，所以今天还挺能理解的。。。推荐给大家，顺便我也做个马克。。。 链接：高级数据结构设计－－并查集及实现学习笔记（有趣篇） - ACShiryu - 博客园  另外里面也有一些相关的题，可以看一看！ 其实要是光把部分的代码放上去看不懂还是并没有什么卵卵用，来道相对（没错就是相对）典型的简单的题吧！ 来人，上题！ 【

题意：有n个学生，编号为0到n-1，m个群，给出每个群的学生，开始学生0被怀疑得了SARS，于是，人传人，被怀疑的学生所属群的所有学生都被怀疑，问共有几个学生被怀疑。 题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=789 ——>>简单的并查集题目，将每个群的后一个学生与前一个学生judge，统计结点数输出即可。

题意 n个学生，分m组，一组中一人有嫌疑则全组都有嫌疑 规定学生0有嫌疑 找出多少人有嫌疑 思路 用并查集把同一个组的人连接起来 查找和f[0]相同的共有多少人即可 代码 #include<stdio.h>#include<math.h>#include<string.h>#include<algorithm>using namespace std;#d