试题 算法训练 连通分块
提交此题 评测记录
资源限制
时间限制：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
解题思路：建图，BFS算法 找连通序列。
AC代码如下：
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;//n个点，m条边
vector<vector<int> > G(10001);
vector<int> res;
int vis[10001];
void ReadInput(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
memset(vis,0,sizeof(vis));
}
void BFS(int S){
vis[S]=1;
queue<int> Q;
Q.push(S);
res.push_back(S);
while(!Q.empty()){
int V=Q.front();
Q.pop();
for(int i=0;i<G[V].size();i++){
int w=G[V][i];
if(vis[w]==0){
vis[w]=1;
res.push_back(w);
Q.push(w);
}
}
}
}
int main(int argc, char** argv) {
ReadInput();
BFS(1);
sort(res.begin(),res.end());
for(int i=0;i<res.size();i++){
cout<<res[i]<<" ";
}
return 0;
}