23-5-4--dfs与bfs--列出连通集

daniel350-wang / 2023-05-05 / 原文

给定一个有

输入格式:

输入第1行给出2个整数

输出格式:

按照"{

输入样例:

输出样例:

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

代码如下：

#include <iostream>
#include <queue>

using namespace std;

struct Node{
    int x,y;
    int step;
}st,ed; 
int a[50][50];
int book[15];
int min=0,n,e;

int dfs(int bgn)
{
    book[bgn]=1;
    cout<<bgn<<' ';
    int i;
    for(int i=0;i<n;i++)
    {
        if(a[bgn][i]==1&&!book[i])
        {
            dfs(i);
        }
    }
}


void bfs(int bgn)
{
    queue <int> q;
    q.push(bgn);
    book[bgn]=1;
    //cout<<bgn<<' ';
    
    while(!q.empty())
    {
        bgn=q.front() ;
        q.pop() ;
    
        cout<<bgn<<' ';
        
        for(int i=0;i<n;i++)
        {
            if(a[bgn][i]==1&&book[i]==0)
            {
                //cout<<i<<' ';
                q.push(i);
                book[i]=1;
                
                
            }
        }
        
    }
    
}

int main()
{
    
    cin>>n>>e;
    for(int i=0;i<e;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        a[x][y]=1;
        a[y][x]=1;
    }
    
    
    for(int i=0;i<n;i++)
    {
        if(!book[i])
        {
            printf("{ ");
            dfs(i);
            printf("}\n");
        }
    }
    for(int i=0;i<n;i++)
    {
        book[i]=0;
    }
    
    for(int i=0;i<n;i++)
    {
        if(!book[i])
        {
            printf("{ ");
            bfs(i);
            printf("}\n");
        }
    }
}