严格定义(摘抄):
对一个图 G=(V,E) 中的两点 x 和 y ,若存在交替的顶点和边的序列
Γ=(x=v0-e1-v1-e2-...-ek-(vk+1)=y) (在有向图中要求有向边vi−( vi+1)属于E ),则两点 x 和 y 是连通的。Γ是一条x到y的连通路径,x和y分别是起点和终点。当 x = y 时,Γ 被称为回路。如果通路 Γ 中的边两两不同,则 Γ 是一条简单通路,否则为一条复杂通路。如果图 G 中每两点间皆连通,则 G 是连通图。
基本方法:
简单的随便从一个点开始bfs,每遍历到一个点都将那个点打好标记,并且统计个数,在bfs退出以后比较统计的连通的点的个数是否等于我们的节点个数,等于则是连通图,不等则不是连通图。
代码如下:
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std; const int maxn = + ; int n,m;
int my_index; vector<int >G[maxn];
bool vis[maxn]; void bfs(int u){
queue<int >Q;
Q.push(u);
while(!Q.empty()){
int s = Q.front();Q.pop();
vis[s] = true;
my_index++;
for(int i = ;i < G[s].size(); i++){
int v = G[s][i];
if(!vis[v])Q.push(v);
}
}
} int main(){
scanf("%d%d",&n,&m);
for(int i = ;i <= m; i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
bfs();
if(my_index == n)printf("Yes\n");
else printf("No\n");
}