2、无向图的各连通分支

系统管理员 2022-04-02 08:47 228阅读 0赞

3.求解无向图的各连通分支

输入：

第一行为图的节点数n（节点编号0至n-1，0<n<=10）  
从第二行开始列出图的边，-1表示输入结束

输出：  
输出每个连通分支的广度优先搜索序列（从连通分支的最小编号开始），不同分支以最小编号递增顺序列出

sample：  
input:  
8  
0 5  
5 2  
4 5  
5 6  
6 2  
3 7  
0 2  
\-1

output：  
0-5-2-4-6  
1  
3-7

#include <stdio.h>
    
    int n;
    int queue[1000], tail = -1, head = 0;
    struct{
        int visited;
        int count;
        int to[18];
    }v[18];
    
    void BFS(){
        int k = queue[head];
        if(v[queue[head]].visited==0){
            v[queue[head]].visited=1;
            printf("-%d",queue[head]);
            head++;
            for(int i=0;i<v[k].count;i++) {
                tail++;
                queue[tail] = v[k].to[i];
            }
        }
        else
            head++;
        return;
    }
    
    int main() {
        
        int x,y;
        scanf("%d",&n);
        
        for(int i=0;i<n;i++){
            v[i].visited=0;
            v[i].count=0;
        }
        
    
        while(1){
            scanf("%d",&x);
            if(x==-1)
                break;
            scanf("%d",&y);
            v[y].to[v[y].count]=x;
            v[y].count++;
            v[x].to[v[x].count]=y;
            v[x].count++;
        }
        
        for(int p = 0; p < n; p++){
            for(int i=0;i<v[p].count;i++)
            for(int j=i+1;j<v[p].count;j++)
                if(v[p].to[i]>v[p].to[j]){
                    int a = v[p].to[i];
                    v[p].to[i]=v[p].to[j];
                    v[p].to[j]=a;
                }
        }
    
        for(int i=0;i<n;i++) {
            if(v[i].visited == 0) {
                queue[head] = i;
                tail = head;
                for(int j=0;j<v[queue[head]].count;j++) {
                        tail++;
                        queue[tail] = v[queue[head]].to[j];
                    }
                v[i].visited = 1;
                printf("%d",i);
                head++;
                while(tail > head || tail == head)
                    BFS();
                printf("\n");
                head = 0;
                tail = -1;
            }
        }
        return 0;
    }