python/TangDou/GraphTheory/CheckConnectivity/bfs.cpp

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