给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N?1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入第1行给出2个整数N(0)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
按照"{ v?1?? v?2?? ... v?k?? }"的格式，每行输出一个连通集。先输出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 }
1 #include<stdio.h> 2 #include<set> 3 #define MAXSIZE 15 4 using namespace std; 5 int n,m; 6 int visited[MAXSIZE]; 7 set<int> mp[MAXSIZE]; 8 void init(){ 9 for(int i = 0; i < MAXSIZE; i++){ 10 visited[i] = 0; 11 } 12 } 13 14 void DFS(int k){ 15 if(visited[k]==1){ 16 return ; 17 } 18 visited[k] = 1; 19 printf(" %d",k); 20 for(set<int>::iterator it = mp[k].begin(); it != mp[k].end(); it++){ 21 DFS(*it); 22 } 23 } 24 void BFS(int k){ 25 visited[k] = 1; 26 printf(" %d",k); 27 int Q[15]; 28 int last = 1; 29 int pre = 0; 30 Q[0] = k; 31 while(pre < last){ 32 int d = Q[pre]; 33 pre++; 34 for(set<int>::iterator it = mp[d].begin(); it != mp[d].end(); it++){ 35 if(visited[*it]==0){ 36 visited[*it] = 1; 37 printf(" %d",*it); 38 Q[last] = *it; 39 last++; 40 } 41 } 42 } 43 } 44 45 int main(){ 46 scanf("%d %d",&n,&m); 47 for(int i = 0; i < m; i++){ 48 int a,b; 49 scanf("%d %d",&a,&b); 50 mp[a].insert(b); 51 mp[b].insert(a); 52 } 53 init(); 54 for(int i = 0; i < n; i++){ 55 if(visited[i]!=1){ 56 printf("{"); 57 DFS(i); 58 printf(" }\n"); 59 } 60 } 61 init(); 62 for(int i = 0; i < n; i++){ 63 if(visited[i]!=1){ 64 printf("{"); 65 BFS(i); 66 printf(" }\n"); 67 } 68 } 69 return 0; 70 }
原文：https://www.cnblogs.com/jinjin-2018/p/8999537.html