P1367 连通图 - 题解

登录注册上岸

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

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

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

成功保外的小孙

2021年8月22日 14:22

并查集

P1367

回复 0 | 赞 0 | 浏览 6.7k

#include<iostream> using namespace std; const int N=1010; int n, m; int p[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { while(cin>>n>>m) { for(int i=1; i<=n; i++) p[i]=i; while(m--) { int a, b; cin>&...

2021年4月25日 16:37

并查集优化（路径压缩+按秩合并）

P1367

回复 0 | 赞 2 | 浏览 6.8k

#include <iostream> using namespace std; const int MAXN = 1005; int fa[MAXN]; //存储每个元素的父节点 int rk[MAXN]; //记录每个根节点对应的树的深度 void init(int n) { //初始化 for(int i = 1;i <= n;i++) { fa[i] = i; rk[i] = 1; } } int Find(int x) { //查找（路径压缩） if(fa[x] == x) return x; ...

2021年1月12日 19:30

并查集实现

P1367

回复 0 | 赞 0 | 浏览 7.3k

#include <iostream> using namespace std; const int maxn=1050; int f[maxn]; int n,m; void init(int n){ for(int i=1;i<=n;i++) f[i]=i; } int find(int x){ if(f[x]==x) return x; else retu...

2021年1月12日 19:14

BFS实现

P1367

回复 0 | 赞 1 | 浏览 7.3k

#include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <queue> using namespace std; int n ,m; int g[1050][1050]; int vis[1050]; int q[1050]; int front=-1; int rear=-1; bool bfs(){ front=-1; ...

题目连通图

题解数量4

热门题解

1 并查集优化（路径压缩+按秩合并）

2 BFS实现

3 并查集实现

4 并查集