题目要求：
给定一个有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的这么多函数，这题我要重点复习^_^