题目要求：

给定一个有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 }

题解： 

        思路如注释所示，可通过所有测试点。 

#include<bits/stdc++.h>
using namespace std;const int MAX_N = 10;
vector<int> adj[MAX_N];
bool visited[MAX_N];  //记录元素是否被访问过void DFS(int v,vector<int> &component){visited[v] = true;component.push_back(v);//按编号递增的顺序访问邻接结点sort(adj[v].begin(),adj[v].end());for(int u : adj[v]){    //把v的邻接点遍历完 if(!visited[u]){DFS(u,component);  //递归}}	
}void BFS(int v,vector<int> &component){queue<int> q;  //用队列辅助进行广度优先搜索q.push(v);visited[v] = true;while(!q.empty()){int u = q.front();q.pop();component.push_back(u);//按编号递增的顺序访问邻接点sort(adj[u].begin(),adj[u].end());for(int w:adj[u]){if(!visited[w]){q.push(w);visited[w] = true;}}	} 
}int main(){int n,m;cin>>n>>m;for(int i =0; i < m; i++){int u,v;              cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);		}	//DFS找连通分量fill(visited, visited+n, false);   //清空visited上的标记 for(int i = 0; i < n; i++){if(!visited[i]){vector<int> component;     //设定一个component变量用来存储一个连通集的所有元素 DFS(i,component);	cout<<"{ ";for(int v:component){cout<<v<<" ";}cout<<"}"<<"\n"; }	}//BFS找连通分量fill(visited,visited+n,false);for(int i = 0;i < n; i++){if(!visited[i]){vector<int> component;BFS(i,component);cout<<"{ ";for(int v:component){cout<<v<<" ";} cout<<"}"<<"\n";}		} return 0;	
}

总结：

        这题用到了很多stl函数，我也是刚学它们的性质，所以这道题很有参考价值。

        1.vector<int> 型数组对此题使用很方便可以直观的存储每个结点的邻接表，而且可以动态的改变大小，太牛了。

        2.fill函数可以直接把数组的给定下标范围统一修改成一个设定值，这题里用来初始化visited[]数组。

        3.sort函数默认从小到大排序，在存储每一个连通集时可以保证题目中所要求的连通性。

        4.“for(int v:component) ”表达式，这是一个输出容器中元素的简洁方法。把每个元素的值赋值给v进行操作。

        5.注意输出格式，每个元素中间隔有space。

        一下包含了stl的这么多函数，这题我要重点复习^_^