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

古城微笑少年丶 2022-06-04 06:10 150阅读 0赞

数据结构实验之图论十：判断给定图是否存在合法拓扑序列  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
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

赵利强

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int MAX = 20;
    
    
    int mp[MAX][MAX];
    int degree[MAX];
    int vt[MAX];
    
    
    int main()
    {
    
        int n, m;
        while (cin >> n >> m)
        {
            int i, j;
            int va, vb;
            memset(degree, 0, sizeof(degree));
            memset(mp, 0, sizeof(mp));
            memset(vt, 0, sizeof(vt));
    
            for (i = 0; i < m; i++)
            {
                cin >> va >> vb;
                mp[va][vb] = 1;
                degree[va]++;
            }
            int flag = 1;
            for (i = 1; i <= n; i++)
            {
                for (j = 1; j <= n; j++)
                {
                    if (!vt[j] && mp[i][j])
                    {
                        degree[i]--;
                    }
                }
                if (degree[i] != 0)
                {
                    flag = 0;
                    break;
                }
                vt[i] = 1;
            }
            if (flag)
                cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        return 0;
    }