数据结构与算法题目集（中文） 7-6 列出连通集-白红宇

数据结构与算法题目集（中文） 7-6 列出连通集

阅读量：3904 次

发布时间：2019-05-23

本文共 1219 字，大约阅读时间需要 4 分钟。

7-6 列出连通集（25 分）

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:

按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

8 60 70 12 04 12 43 5

输出样例:

{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }

一开始用结构体做的，然后提交发现只有唯一的答案，发现事情并不简单，然后看了别人的存储方式方才恍然大悟。以后要好好学习数据结构啊。。。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int n,e;int Map[15];int road[15];int num;int locc[15][15];void dfs (int c){     road[num++]=c;     Map[c]=1;    for (int i=0;i

q; q.push(c); int temp; while (!q.empty()) { temp=q.front(); q.pop(); for (int i=0;i

其实可以直接printf的，建了个数组花里胡哨。。。

第二次做的代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=15;int n,e;int edge[maxn][maxn];int vis[maxn];vector 
         
           re;void init(){ memset (edge,0,sizeof(edge));}void dfs (int x){ vis[x]=1; re.push_back(x); for (int i=0;i

q; vis[s]=1; re.push_back(s); q.push(s); while (!q.empty()) { int now=q.front(); q.pop(); for (int i=0;i

转载地址：http://pjaen.baihongyu.com/