网站突然打不开了,享设计官网,莱芜杂谈莱芜话题,个人音乐网站源码06-图1 列出连通集#xff08;25 分#xff09;给定一个有N个顶点和E条边的无向图#xff0c;请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时#xff0c;假设我们总是从编号最小的顶点出发#xff0c;按编号递增的顺序访问邻接点。输入格式:输入… 06-图1 列出连通集25 分给定一个有N个顶点和E条边的无向图请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时假设我们总是从编号最小的顶点出发按编号递增的顺序访问邻接点。输入格式:输入第1行给出2个整数N(0N≤10)和E分别是图的顶点数和边数。随后E行每行给出一条边的两个端点。每行中的数字之间用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 set
#include cmath
#include queue
#include stack
#include vector
#include string
#include cstdio
#include cstdlib
#include cstring
#include iostream
#include algorithm
#include functional#define mod 1000000007
const int INF 0x7f7f7f7f;
typedef long long ll;
const int maxn 10050;
using namespace std;int m, n;
bool mp[15][15];
bool visd[15];
bool visb[15];void dfs(int x)
{visd[x] true;printf(%d , x);for(int i 0; i m; i){if(mp[x][i] !visd[i])dfs(i);}
}
void bfs(int x)
{queueint que;que.push(x);visb[x] true;while(!que.empty()){int n que.front();que.pop();printf(%d , n);for(int i 0; i m; i){if(mp[n][i] !visb[i]){visb[i] true;que.push(i);}}}}
int main()
{scanf(%d%d, m, n);memset(mp, 0, sizeof(mp));memset(visb, 0, sizeof(visb));memset(visd, 0, sizeof(visd));while(n--){int t1, t2;scanf(%d%d, t1, t2);mp[t1][t2] true;mp[t2][t1] true;}for(int i 0; i m; i){if(!visd[i]){printf({ );dfs(i);printf(}\n);}}for(int i 0; i m; i){if(!visb[i]){printf({ );bfs(i);printf(}\n);}}return 0;
}转载于:https://www.cnblogs.com/focus5679/p/9286137.html
