图的连通性判断（并查集+Bfs+Dfs+Floyd）

有向图的连通性检查共4种方法,并查集性能最高，代码也短，优先推荐：

一、并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; //图的最大点数量
/**
 共提供两组数据，样例1为不连通用例，样例2为连通用例

 样例1：不连通，5号结点为独立的
 5 4
 1 2
 2 3
 3 4
 1 4

 样例2：连通，不存在独立结点
 5 4
 1 2
 2 3
 3 4
 1 5

 检测各种算法是否能准确获取结果
 */
int n;      //n个人
int m;      //m个亲戚
int p;      //询问p对亲戚关系
int x, y;   //输入两个人之间的关系
int fa[N];  //并查集数组
//要深入理解这个递归并压缩的过程
int find(int x) {
    if (fa[x] != x)//如果x不是族长,递归找父亲,副产品就是找回的结果更新掉自己的家族信息。
        fa[x] = find(fa[x]);//非常经典的更新,路径压缩大法！
    //返回族长是谁
    return fa[x];
}

//加入家族集合中
void join(int c1, int c2) {
    int f1 = find(c1), f2 = find(c2);
    if (f1 != f2)fa[f1] = f2;//各自找家长，如果家长不一样，就把C1的族长，认C2的族长为爸爸,C1的族长强烈表示不满意
}

int cnt;

int main() {
    //n个人员，m个关系
    cin >> n >> m;
    //并查集初始化
    for (int i = 1; i <= n; i++)fa[i] = i; //自己是自己的老大
    //录入m种关系,使用并查集来判断图的连通性
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        //加入并查集
        join(x, y);
    }
    //图已经搭好了，接下来看它们根节点是否相同，如只有一个相同的根节点，则说明是一个连通图
    for (int i = 1; i <= n; i++) if (fa[i] == i)cnt++;
    if (cnt == 1)printf("图是连通的
");
    else printf("图不是连通的
");
    return 0;
}

二、dfs

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; //图的最大点数量
struct Edge {       //记录边的终点，边权的结构体
    int to;         //终点
    int value;      //边权
};
int n, m; //表示图中有n个点，m条边
vector<Edge> p[N];  //使用vector的邻接表
/**
 共提供两组数据，样例1为不连通用例，样例2为连通用例

 样例1：不连通，5号结点为独立的
 5 4
 1 2
 2 3
 3 4
 1 4

 样例2：连通，不存在独立结点
 5 4
 1 2
 2 3
 3 4
 1 5

 检测各种算法是否能准确获取结果
 */
bool st[N];

int cnt;

//深度遍历
void dfs(int u) {
    st[u] = true;
    cnt++;//多走了一个结点
    for (int i = 0; i < p[u].size(); i++) {
        int x = p[u][i].to;
        if (!st[x]) dfs(x);
    }
}

int main() {
    //采用邻接表建图
    cin >> n >> m;
    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        p[u].push_back({v, 1});//因本题不需要权值，默认权值为1
    }

    //利用dfs进行检查是不是强连通的
    dfs(1);

    if (cnt == n) printf("图是连通的
");
    else printf("图不是连通的
");
    return 0;
}

三、bfs

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; //图的最大点数量
struct Edge {       //记录边的终点，边权的结构体
    int to;         //终点
    int value;      //边权
};
int n, m; //表示图中有n个点，m条边
vector<Edge> p[N];  //使用vector的邻接表
/**
 共提供两组数据，样例1为不连通用例，样例2为连通用例

 样例1：不连通，5号结点为独立的
 5 4
 1 2
 2 3
 3 4
 1 4

 样例2：连通，不存在独立结点
 5 4
 1 2
 2 3
 3 4
 1 5

 检测各种算法是否能准确获取结果
 */
bool st[N];

int cnt;

int main() {
    //采用邻接表建图
    cin >> n >> m;
    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        p[u].push_back({v, 1});//因本题不需要权值，默认权值为1
    }
    //利用bfs进行检查是不是强连通的
    //把1号结点放入队列
    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        st[u] = true;
        cnt++;

        for (int i = 0; i < p[u].size(); i++) {
            int x = p[u][i].to;
            if (!st[x]) q.push(x);
        }
    }

    if (cnt == n) printf("图是连通的
");
    else printf("图不是连通的
");
    return 0;
}

四、floyd

#include <bits/stdc++.h>

using namespace std;

const int N = 1010; //图的最大点数量
int n, m;
/**
 共提供两组数据，样例1为不连通用例，样例2为连通用例

 样例1：不连通，5号结点为独立的
 5 4
 1 2
 2 3
 3 4
 1 4

 样例2：连通，不存在独立结点
 5 4
 1 2
 2 3
 3 4
 1 5

 检测各种算法是否能准确获取结果
 */

//用floyd来判断起点是否可以达到终点
int dis[N][N];        //邻接矩阵
void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
}

int main() {
    //采用邻接矩阵建图
    cin >> n >> m;
    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        //双向建边
        dis[u][v] = 1;
        dis[v][u] = 1;
    }
    //调用floyd
    floyd();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!dis[i][j]) {
                printf("图不是连通的
");
                cout << i << " " << j << endl;
                exit(0);
            }
    printf("图是连通的
");
    return 0;
}