本文共 1764 字，大约阅读时间需要 5 分钟。
题意：如果无向图 G每对顶点v和w都有从v到w的路径，那么称无向图G是连通的。现在给定一张无向图，判断它是否是连通的。第一行有 2 个整数 n,m(0<n,m<10^6)。接下来m行每行有 2 个整数u,v表示u和v有边连接。 代码：//bfs#include#include #include #include #include #include using namespace std;#define MAXN 1000000vector a[MAXN];int vis[MAXN];queue q; void bfs(int vt){ q.push(vt); while(q.size()){ int t=q.front(); q.pop(); for(int i:a[t]){ if(!vis[i]){ vis[i]=1; q.push(i); } } }}int main(){ int n,m; cin>>n>>m; int u,v; for(int i=1;i<=m;i++){ cin>>u>>v; a[u].push_back(v); a[v].push_back(u); } vis[1]=1; bfs(1); int flag=0; for(int i=1;i<=n;i++){ if(vis[i]==0){ flag=1; } } if(flag){ cout<<"no"<
//DFS#include#include #include #include #include #include using namespace std;#define MAXN 1000000vector a[MAXN];int vis[MAXN];queue q; void dfs(int vt){ for(int i:a[vt]){ if(!vis[i]){ vis[i]=1; dfs(i); } }}int main(){ int n,m; cin>>n>>m; int u,v; for(int i=1;i<=m;i++){ cin>>u>>v; a[u].push_back(v); a[v].push_back(u); } vis[1]=1; dfs(1); int flag=0; for(int i=1;i<=n;i++){ if(vis[i]==0){ flag=1; } } if(flag){ cout<<"no"<
//并查集#include#include #include #include #include #include using namespace std;#define MAXN 1000000vector a[MAXN];int f[MAXN],n;void init(){ for(int i=1;i<=n;i++){ f[i]=i; }}int find(int x){ if(x!=f[x]){ f[x]=find(f[x]); } return f[x];}void combine(int x,int y){ int tx=find(x); int ty=find(y); if(tx!=ty){ f[tx]=ty; }}int main(){ int m; cin>>n>>m; init(); int u,v; for(int i=1;i<=m;i++){ cin>>u>>v; combine(u,v); } int cnt=0; for(int i=1;i<=n;i++){ if(f[i]==i){ cnt++; } } if(cnt==1){ cout<<"yes"<
转载地址：http://apnki.baihongyu.com/