图结构练习——判断给定图是否存在合法拓扑序列

左手的ㄟ右手 2022-07-12 09:19 129阅读 0赞

[sdut原题链接][sdut]

图结构练习——判断给定图是否存在合法拓扑序列  
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

Hint

Author  
赵利强

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    int op, tp, n, m;
    int link[14], map[14][14], indegree[14];
    //拓扑排序算法核心语句
    void topo()
    {
        for(int i = 1; i <= n; i++)//寻找入度为零的点
        {
            if(indegree[i] == 0)//判断是否是入度为零的点
                link[tp++] = i;//将入度为零的点入队
        }
        while(op < tp)//更新的过程
        {
            for(int i = 1; i <= n; i++)//寻找入度为当前队列结点的点的点
            {
                if(map[link[op]][i] == 1)//判断是否入度为当前队列结点
                {
                    indegree[i]--;//结点入度数目更新
                    if(indegree[i] == 0)//判断更新后是否有入度为零的点
                        link[tp++] = i;//将更新后入度为零的点入队
                }
            }
            op++;//当前队列结点出队
        }
        if(op == n)//判断出队结点数是否是总结点数，若是，则为合法拓扑序列，若不是，则存在有向回路
            printf("YES\n");
        else
            printf("NO\n");
    }
    int main()
    {
        int u, v;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            op = tp = 0;//队列标记变量初始化
            memset(map, 0, sizeof(map));//map数组初始化
            memset(indegree, 0, sizeof(indegree));//indegree数组（记录结点入度数目）初始化
            for(int i = 1; i <= m; i++)
            {
                scanf("%d %d", &u, &v);
                map[u][v] = 1;
                indegree[v] += 1;
            }
            topo();
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-02-20 09:37:18
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2017/pid/2140