题目
题目描述:给你一个 n 个点,m 条边的无向图,求至少要在这个的基础上加多少条无向边使得任意两个点可达~
输入描述:
第一行两个正整数 n 和 m 。
接下来的m行中,每行两个正整数 i 、 j ,表示点i与点j之间有一条无向道路。
输出描述:
输出一个整数,表示答案
解析
1)知识点
- 这道题是一道基础的dfs或并查集,一开始我是想这么说的。但是我发现题目吧dfs压死了。
- 因为dfs遍历标记用的空间在并查集的五倍,所以会MLE(代码依旧放下面了)。
2)看题目
- 题目的意思就是让我们在已知一些边的情况下,把剩下的连成一张连通图。
3)算法分析
- 这道题很简单,我们要连成一张连通图只要求这个图有几个联通分量就行了。
- 因为两个联通分量之间只要加一条边,就可以互通了。
- 求联通分量当然就可以遍历搜索然后标记。也就可以用并查集。
- 并查集简单来说就是给一个节点找父亲,每个节点都有自己的父亲。单个节点自己就是自己的父亲。
- 然后祖宗(总会有个起源的祖宗)一样就是一家人。
4)算法操作
- 首先就是找祖宗(内含路径压缩):
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } //fa[x] = find(fa[x])就是路径压缩,就是让父亲直接变成起源祖宗,以后查找就快了
- 然后就是合并在一起,就是让起源祖宗换人:
void merge(int x, int y) { x = find(x); y = find(y); if (x != y) { fa[x] = y; } }
5)打代码
- 就先初始化节点父亲(为自己)。
- 然后开始结合。
- 接下来看有几个人祖宗是自己,就有几个连通块了。
- 减个一输出就好了。
- 下面全代码~
MLE代码
#include <iostream> #include <cstring> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 1e5 + 7; int head[MAX], tot; struct EDGE { int v, next; } edge[MAX << 1]; int n, m; int vis[MAX]; //全局变量区 void init();//前向星初始化 void add_edge(int u, int v);//前向星加边 void dfs(int u, int fa);//前向星dfs //函数预定义区 int main() { IOS; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; add_edge(u, v); add_edge(v, u); } int ans = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) { ans++; dfs(i, 0); } } cout << ans - 1 << endl; return 0; } void init() { memset(head, 0, sizeof head); tot = 0; } void add_edge(int u, int v) { tot++; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot; } void dfs(int u, int fa) { vis[u] = 1; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].v; if (v == fa) continue; dfs(v, u); } } //函数区
AC代码
#include <iostream> #include <cstring> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 1e5 + 7; int n, m; int fa[MAX]; //全局变量区 int find(int x); void merge(int x, int y); //函数预定义区 int main() { IOS; cin >> n >> m; for (int i = 1; i <= n; i++) { fa[i] = i; } for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; merge(u, v); } int ans = 0; for (int i = 1; i <= n; i++) { if (i == find(i)) { ans++; } } cout << ans - 1 << endl; return 0; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void merge(int x, int y) { x = find(x); y = find(y); if (x != y) { fa[x] = y; } } //函数区