作者 陈越
单位 浙江大学
给定一个有 n 个顶点和 m 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第 1 行给出 2 个整数 n (0<n≤10) 和 m，分别是图的顶点数和边数。随后 m 行，每行给出一条边的两个端点。每行中的数字之间用 1 空格分隔。
输出格式:
按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出 DFS 的结果，再输出 BFS 的结果。
输入样例:
8 6 0 7 0 1 2 0 4 1 2 4 3 5输出样例:
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include<bits/stdc++.h>
using namespace std;
bool G[11][11],st[11];
int n,m;
int path[11],cnt,idx;
queue<int>q;
void dfs(int idx){path[cnt++]=idx;st[idx]=true;for(int i=0;i<n;i++)if(st[i]==false&&G[idx][i])dfs(i);
}
void bfs(int idx){q.push(idx);st[idx]=true;//压入就要设置为已遍历while(q.size()){int t=q.front();q.pop();path[cnt++]=t;for(int i=0;i<n;i++)if(st[i]==false&&G[t][i]){//监测t的邻居iq.push(i);st[i]=true;//必须在压入的时候就设置为遍历过，等到取出再设置可能已经压入多次}}
}
int main(){cin>>n>>m;for(int i=0;i<m;i++){int a,b;cin>>a>>b;G[a][b]=1;G[b][a]=1;}idx=cnt=0;while(1){while(st[idx])idx++;if(idx==n)break;cnt=0;dfs(idx);cout<<"{ ";for(int i=0;i<cnt;i++)cout<<path[i]<<" ";cout<<"}"<<endl;}idx=cnt=0;fill(st,st+n,false);while(1){while(st[idx])idx++;if(idx==n)break;cnt=0;bfs(idx);cout<<"{ ";for(int i=0;i<cnt;i++)cout<<path[i]<<" ";cout<<"}"<<endl;}return 0;
}
