题目

题目描述：
给你一个 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;
    }
}
//函数区

【练习】加边的无向图

题目

解析

1）知识点

2）看题目

3）算法分析

4）算法操作

5）打代码

MLE代码

AC代码

全站热榜