06-图1 列出连通集

题意：给出一个无向图，分别用dfs和bfs找出图中的连通块。连通块按从小到大的顺序输出。

思路：
dfs和bfs遍历一遍图可以找出一个连通块，只需分别以每个点为起点进行dfs或bfs，就能找出所有连通块。因为是找连通块，标记的点不用复原，已经标记过的点不用再搜索。dfs遍历过程中可以把数存到数组里，bfs可以用队列优化遍历过程中直接输出遍历到的点。

代码：

#include<bits/stdc++.h>
using namespace std;
// typedef struct node{
//     int x[100],cnt;
// }node;
int mp[100][100],x[100],cnt,m,n,vis[100];
void dfs(int s)
{
//	printf("^^^^%d\n",m);
//	vis[s]=1;for(int i=0;i<m;i++){
//    	printf("%d %d\n",vis[i],mp[s][i]);if(vis[i]==0&&mp[s][i]){
//        	printf("****\n");x[cnt++]=i;vis[i]=1;dfs(i);}}
}
void bfs(int sum)
{queue<int>q;q.push(sum);vis[sum]=1;printf("{ ");while(!q.empty()){int p=q.front();printf("%d ",p);q.pop();for(int i=0;i<m;i++){if(!vis[i]&&mp[p][i]){q.push(i);vis[i]=1;}}}printf("}");
}
int main()
{int a,b;memset(mp,0,sizeof(mp));memset(vis,0,sizeof(vis));scanf("%d%d",&m,&n);for(int i=0;i<n;i++){scanf("%d%d",&a,&b);mp[b][a]=mp[a][b]=1;}for(int i=0;i<m;i++){if(vis[i]){continue;}cnt=0;vis[i]=1;x[cnt++]=i;dfs(i);
//        printf("@@@\n");if(cnt>0){printf("{ ");}for(int j=0;j<cnt;j++){printf("%d ",x[j]);}printf("}\n");}memset(vis,0,sizeof(vis));for(int i=0;i<m;i++){if(!vis[i]){bfs(i);printf("\n");}}return 0;
}