POJ 1611 The Suspects（并查集）
source link: https://arminli.com/poj1611/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
POJ 1611 The Suspects（并查集）
November 28, 2015
题意：非典时期，共有 n 个人（标号 0~n-1），分成 m 组。第一行输入 n（0 < n <= 30000），m（0 <= m <= 500），接下来 m 行代表 m 组，每行第一个数 k 代表该组人数，后面 k 个数为这 k 个人的标号。默认标号为 0 的人是流感嫌疑人，如果一个小组中有 一个人是嫌疑人，那么这个组的所有人都成为了流感嫌疑人。一个人可以在几个小组里。问共有多少个嫌疑人。 [c] #include #include #include #include #include using namespace std; //rank[i]代表标号为 i 的人在链中第几位 //例如最后一个节点的 rank 为 1，它的父节点的 rank 就是 2 int rank[30005]; int fa[30005]; //找祖先 int findfa(int x){ if(fa[x] != x){ fa[x] = findfa(fa[x]); } return fa[x]; } //合并 void add(int x, int y){ x = findfa(x); y = findfa(y); if(x != y){ //如果这两个点还没有被合并 if(rank[x] >= rank[y]){ fa[y] = x; rank[x] += rank[y]; }else{ fa[x] = y; rank[y] += rank[x]; } } } int main() { int n, m; while(scanf(“%d %d”, &n, &m) != EOF){ if(n == 0 && m == 0) break; for(int i = 0; i < n; i++){ fa[i] = i; rank[i] = 1; //初始化所有点 } while(m—){ int num, first; scanf(“%d %d”, &num, &first); for(int i = 1; i < num; i++){ int temp; scanf(“%d”, &temp); add(first, temp); } } printf(“%dn”, rank[fa[0]]); } return 0; } [/c]
Recommend
-
37
详解并查集 Powered by WSY in SSF 2019-11-02 13:46 【1】并查集的定义： 并查集（Disjoint Set）是一种非常精巧的非常实用的数据结构，它主要用来处理一些不相交集合...
-
28
预计阅读时间： 10 分钟 今天讲讲 Union-Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。名词很高端，其实特别好理解，等会解释，另外这个...
-
22
地址 https://www.acwing.com/problem/content/241/ 小A和小B在玩一个游戏。 首先，小A写了一个由0和1组成的序列S，长度为N。 然后，小B向小A提出...
-
36
开始填坑力 引 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。带路径压缩的并查集的时间复杂度已被证明是 \(O(\alpha(n))\) 的。这个函数的值在当 \(n\...
-
34
【并查集】一种与时间赛跑的巧妙算法 引入：（NOIP模拟题）极端寒冬 （不要求刚刚接触并查集的读者完全明白本题） 先了解一下并查集是个什么东西： 合并两点所在集合和 查找两点是否...
-
11
Armin's BlogVIJOS-P1045 Kerry的电缆网络（并查集）February 24, 2016题目链接 按照长度排序，然后并查集即可。 #include<cstring> #incl...
-
13
Armin's BlogPOJ 2524 Ubiquitous Religions（并查集）November 29, 2015题目链接 题意：调查学校的学生宗教信仰情况，第一行输入 n（总人数）和 m，...
-
9
Armin's BlogHDU 1232 畅通工程（并查集）November 30, 2015题目链接 中文题，最简单的并查集。午休时间怒 A 一发~ #inclu...
-
5
Computer Science > Computation and Language [Submitted on 5 Nov 2016 (v1), last revised 21 Jun 2018 (this version, v6...
-
13
Zabbix, selinux and CentOS 7.3.1611If you're using CentOS, you probably noticed that we have a CR repository containing all the built packages for the next minor releas...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK