列出连通集(mooc)

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

思路：掌握DFS和BFS。

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define max 100

int G[max][max];

int vis[max];

void DFS(int v,int n){

  vis[v]=;

  printf(" %d",v);

  for(int i=;i<n;i++){

    if(vis[i]==&&G[v][i]>){

      DFS(i,n);

    }

  }

}

void BFS(int v,int n){

  vis[v]=;

  queue<int> q;

  q.push(v);

  while(!q.empty()){

    int j=q.front();

    q.pop();

    printf(" %d",j);

    for(int i=;i<n;i++){

      if(G[j][i]&&!vis[i]){

        vis[i]=;

        q.push(i);

      }

    }

  }

}

int main(){

  int n,e;

  scanf("%d %d",&n,&e);

  memset(vis,,sizeof(vis));

  int v1,v2,i;

  for(i=;i<e;i++){

    scanf("%d %d",&v1,&v2);

    getchar();

    G[v1][v2]=G[v2][v1]=;

  }

  //DFS

  for(i=;i<n;i++){

    if(!vis[i]){

      printf("{");

      DFS(i,n);

      printf(" }\n");

    }

  }

  //BFS

  memset(vis,,sizeof(vis));

  for(i=;i<n;i++){

    if(!vis[i]){

    printf("{");

    BFS(i,n);

    printf(" }\n");

    }

  }

  return ;

}