SDUT 判断给定图是否存在合法拓扑序列

seven_ • 2023年2月21日下午10:12 • Python • 阅读 283

题目描述

Problem Description

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。
Input

输入包含多组，每组格式如下。
第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)
后面m行每行两个整数a b，表示从a到b有一条有向边。

Output

若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

Sample Input

1 0
2 2
1 2
2 1
Sample Output

YES
NO

分析 & 代码

拓扑排序问题思路就是找到一个入度为0的点a，然后把以这个点为起点的点的入度都减少一，然后判断这个时候是否又出现了入度为0的点，反复这个过程，知道没有入度为0的点结束如果所有的点此时入度都是0那么这个图中就有至少一条合法的拓扑路径否则就没有。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
int n,m;
int indegree[15];         //保存入度为0的点
int vis;                  //计数
vector<int> g[15];         //邻接表的方式储存边信息

int topo(){
    queue<int> sav;
    for(int i=1; i<=n; i++){
        if(indegree[i]==0)
            sav.push(i);
    }                             //第一次将入度为0的点加入队列    这个地方队列只是保存一下 像链表等结构都可以
    while(!sav.empty()){
        int temp = sav.front();
        sav.pop();                   //取出一个入度为0的点 然后把以这个点为起始点的边删掉  (a,b)其实就是b的indegree减一
        int len = g[temp].size();
        vis++;
        for(int i=0; i<len; i++){
            indegree[g[temp][i]]--;     //temp 也就是此时入度为0的点  以这个点开头的点入度都减一
            if(indegree[g[temp][i]]==0){     //判断一下是否又产生了新的入度为0的点 有的话加入进去
                sav.push(g[temp][i]);
            }
        }
    }
}
int main(){
    int a,b;
    while(cin>>n>>m){

        vis = 0;
        memset(indegree, 0, sizeof(indegree));
        for(int i=0; i<15; i++){
            g[i].clear();
        }                                          //日常初始化

        for(int i=0; i<m; i++){
            cin>>a>>b;
            indegree[b]++;                   //边输入 边统计入度
            g[a].push_back(b);
        }
        topo();
        if(vis==n)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}