python/TangDou/GraphTheory/CheckConnectivity/floyd.cpp

#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("图不是连通的\n");
                cout << i << " " << j << endl;
                exit(0);
            }
    printf("图是连通的\n");
    return 0;
}