P1319 畅通工程2 - 题解

登录注册上岸

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

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

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

2024年3月13日 10:10

畅通工程2 题解：并查集

P1319

回复 0 | 赞 0 | 浏览 455

#include <iostream> #include <cstdio> using namespace std; int fa[1005]; int find(int x){ if(x == fa[x]){ return x; } return fa[x] = find(fa[x]); } int main() { int n,m; while(cin >> n >> m){ if(n == 0){ ...

2023年6月22日 22:09

模板题

P1319

回复 0 | 赞 2 | 浏览 1.1k

#include<bits/stdc++.h> #define rep(i,s,e) for(int i=s;i<e;i++) #define per(i,s,e) for(int i=s;i>e;i--) using namespace std; #define MAXN 1005 int fa[MAXN];//fa[x]是x的父节点，初始化设为自己 void init(int n){//初始化每个节点的父节点为他自己 for(int i=1;i<=n;i++) fa[i]=i; } int find(int i)...

我才不怕编程

2023年3月17日 15:28

连通分量个数-->dfs

P1319

回复 0 | 赞 1 | 浏览 2.1k

#include <bits/stdc++.h> using namespace std; vector<int> neibor[1000];//neibor[i]：结点i的邻居们 int visit[1000];//visit[i]：结点i是否被访问过 void dfs(int x) { visit[x]=1; for(int i=0;i<neibor[x].size();i++){ if(visit[neibor[x][i]]==0) dfs(neibor[x][i]); } } int main()...

努力努力在努力

2023年2月24日 20:10

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

P1319

回复 0 | 赞 1 | 浏览 3.1k

#include <algorithm> #include <bits/stdc++.h> #include <cmath> #include <cstdio> #include <cstdlib> #include <math.h> #include <queue> #include <string> using namespace std; int fa[1002]; int find(int...

2022年6月29日 23:23

并查集，注释应该清楚

P1319

回复 0 | 赞 2 | 浏览 4.7k

有关并查集的两篇文章觉得还不错： https://blog.csdn.net/yuanmartin/article/details/108489016 https://blog.csdn.net/m0_50966319/article/details/124252266 #include <iostream> #include <vector> using namespace std; const int len = 1005; // fa[i] 表示节点i所在集合的根节点是什么。 int fa[len]; ...

2021年5月27日 20:14

DreamJudge1312_kruskal算法

P1319

回复 0 | 赞 1 | 浏览 8.9k

Kruskal 求解的是全图连通的最低成本，即使为了保证图中的任意两点连通，所需要的最小花费 Kruskal = 贪心策略 + 并查集其实Kruskal 就是利用了并查集的特点，并查集可以通过输入的边来判断其是否为连通图所必要的边，如果是那么进行连接，不必要掠过如果再将输入边的权值按从小到大排列，那么并查集记录的就是使图联通的必要的最小边的集合，即最小生成树，其权值和即为所求 sum 记录权值和，total 记录输入边中为必要的连通的边为多少，若 total < N -1 ，那么图不连通，就更谈不上最小生成树注意：并查集：find() ...

2021年5月27日 17:00

DreamJudge1319_并查集

P1319

回复 0 | 赞 1 | 浏览 6.8k

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

2021年4月22日 17:42

并查集模板题

P1319

回复 0 | 赞 0 | 浏览 8.0k

#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<...

题目畅通工程2

题解数量8

热门题解

1 并查集，注释应该清楚

2 模板题

3 连通分量个数-->dfs

4 DreamJudge1319_并查集

5 DreamJudge1312_kruskal算法

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

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

8 并查集模板题