#include using namespace std; const int N = 1010; //图的最大点数量 struct Edge { //记录边的终点,边权的结构体 int to; //终点 int value; //边权 }; int n, m; //表示图中有n个点,m条边 vector 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("图是连通的\n"); else printf("图不是连通的\n"); return 0; }