蓝桥杯 算法训练 连通块
题目：
资源限制
时间限制：200ms 内存限制：8.0MB
问题描述
连通分块
输入格式
输入的第一行包含两个整数n, m
n代表图中的点的个数，m代表边的个数
接下来m行，每行2个正整数，表示图中连通的两点。
输出格式
输出1行，与1连通的点的集合，并按升序排列输出。
样例输入
6 3
1 2
2 3
3 4
样例输出
1 2 3 4
数据规模和约定
n<=10000,m<=100000
DFS做法（复杂度高）：
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<int> ans;
void dfs(vector<int> v[],int vis[],int x,int y){
for(int i=0;i<v[x].size();i++){
if(v[x][i]==y) {
ans.push_back(y);//将直接邻居的点放入储存结果的vector容器中
return;
}
}
vis[x]=1;
for(int i=0;i<v[x].size();i++){//通过当前直接邻居去找直接邻居的直接邻居
if(!vis[v[x][i]])
dfs(v,vis,v[x][i],y);
}
vis[x]=0;
}
int main(){
int n,m;
cin>>n>>m;
int vis[n+1];
memset(vis,0,sizeof(vis));
vector<int> v[n+1];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);//邻接表
v[b].push_back(a);
}
ans.push_back(1);
for(int i=2;i<=n;i++){//枚举各个点 查看是否连通
dfs(v,vis,1,i);
}
for(int i=1;i<ans.size();i++){//排序
if(ans[i]<ans[i-1]){
int t=ans[i];
ans[i]=ans[i-1];
ans[i-1]=t;
}
}
for(int i=0;i<ans.size();i++){//去重
if(ans[i]==ans[i-1]) continue;
cout<<ans[i]<<" ";
}
return 0;
}
BFS做法：
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
vector<int> ans;
queue<int> q;
void bfs(vector<int> v[],int vis[],int x){//BFS是通过队列来进行的，将与1直接领居的点全部放入队列，再将直接领居的直接领居放入
q.push(x);
while(!q.empty()){
int y=q.front();
q.pop();
vis[y]=1;
ans.push_back(y);
for(int i=0;i<v[y].size();i++){
if(!vis[v[y][i]]) q.push(v[y][i]);
}
}
}
int main(){
int n,m;
cin>>n>>m;
int vis[n+1];
memset(vis,0,sizeof(vis));
vector<int> v[n+1];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
bfs(v,vis,1);
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
if(ans[i]==ans[i-1]) continue;
cout<<ans[i]<<" ";
}
return 0;
}
版权声明：本文为ljmmm1原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。