P1319 畅通工程2 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2021年5月27日 17:00

DreamJudge1319_并查集

P1319

回复 0 | 赞 3 | 浏览 7.5k

并查集可以看作一棵棵树组成的森林每棵树实际都为图的一个连通图已知，有N个点，那么把所有点都连通的最少边为 N-1 由于这些树内部都是连通的，可以把这些树看成一个新的点，最后看有几个点，假设为M,那么最少需要M-1条边能把整个图变成一个连通图程序的关键点：find() 函数，注意 fa[x] = find(fa[x])是进行路径压缩的功能。初始化，每个点的父亲为本身注意理解sum 是什么，sum 是记录，将两个树连接到一起的次数，也就是必不可少的边有多少个而如果读入一条新的边，连接的是某棵树中的点之间的边，那么对于这条边对于整体的连通并没有什...

2021年4月22日 17:42

并查集模板题

P1319

回复 0 | 赞 2 | 浏览 9.1k

#include<iostream> #include<string> #include<algorithm> #include<vector> using namespace std; const int MAXN = 1e3+3; int father[MAXN]; int find(int x){ return x==father[x]?x:(father[x]=find(father[x])); } void init(int N){ for(int i=1;i<...

1
2

题目畅通工程2

题解数量12

发布题解在线答疑

热门题解

1 模板题

2 并查集，注释应该清楚

3 畅通工程（并查集-路径压缩）模板题解：

4 畅通工程2 题解：并查集

5 DreamJudge1319_并查集

6 畅通工程2，对于并查集理解

7 连通分量个数-->dfs

8 畅通工程2 题解：c++

9 并查集模板题

10 并查集模版