数据结构实验之图论十：判断给定图是否存在合法拓扑序列

小灰灰 2022-06-04 03:30 113阅读 0赞

### 数据结构实验之图论十：判断给定图是否存在合法拓扑序列 ###

Time Limit: 1000MS  Memory Limit: 65536KB

#### Problem Description ####

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

#### Input ####

输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

#### Output ####

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

#### Example Input ####

1 0
    2 2
    1 2
    2 1

#### Example Output ####

YES
    NO
    
     #include<stdio.h>
    #include<string.h>
    #define maxn 15
    #define max 0x3f3f3f3f
    
    int dt[maxn][maxn];
    int inDegree[maxn];
    int queue[maxn];
    int front,rear;
    
    void TopSort(int n)
    {
        int i;
        int u;
        int cnt = 0;
        for(i=1;i<=n;i++)
        {
            if(inDegree[i]==0)
            {
                queue[++rear] = i;
            }
        }
        while(front!=rear)
        {
            u = queue[++front];
            cnt++;
            for(i=1;i<=n;i++)
            {
                if(dt[u][i])
                {
                    inDegree[i]--;
                    if(inDegree[i] == 0)
                    {
                        queue[++rear] = i;
                    }
                }
            }
        }
        if(cnt == n)
        {
            printf("0\n");
        }
        else
        {
            printf("1\n");
        }
    }
    
    int main()
    {
        int n,m;
        int u,v;
        int t;
        scanf("%d",&t);
        while(t--)
        {
            front = rear = -1;
            memset(dt,0,sizeof(dt));
            memset(inDegree,0,sizeof(inDegree));
            scanf("%d%d",&n,&m);
            while(m--)
            {
                scanf("%d%d",&u,&v);
                dt[u][v] = 1;
                inDegree[v] ++;
            }
            TopSort(n);
        }
        return 0;
    }