PAT甲级1146Topological Order

Posted on | | Visitors:
Words count in article: 487 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805343043829760

题解

题目要求

给定一个有向图，请判断一个序列是否是该有向图的拓扑序列。

  • 输入

    • N：正整数，不超过1000，图中顶点的数量，顶点索引为[1,N]
    • M：正整数，不超过10000，有向边的数量
    • M条有向边：开始顶点索引、结束顶点索引
    • K：不超过100，待检验的序列的个数
    • K个序列：索引为[0,K]

  • 输出

    对于每个排列，如果不是拓扑排序则输出其索引

解题思路

  1. 保存每个结点的前驱结点
  2. 使用一维数组保存每个结点是否已访问
  3. 遍历序列判断每个结点的前驱结点是否已访问，如果未访问，则该序列不是拓扑序列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// Problem: PAT Advanced 1146
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805343043829760
// Tags: 拓扑序列 图

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> before;

int main()
{
    int n, m, k;
    scanf("%d %d", &n, &m);
    before.resize(n+1);

    int v1, v2;
    for (int i = 0; i < m; i++){
        scanf("%d %d", &v1, &v2);
        before[v2].push_back(v1);
    }

    scanf("%d", &k);
    vector<int> result;
    for (int i = 0; i < k; i++){ // 判断k个序列
        // 保存一个序列
        vector<int> sequence(n);
        for (int j = 0; j < n; j++){
            scanf("%d", &sequence[j]);
        }
        // 判断该序列是否是拓扑序列
        vector<bool> visited(n + 1, false);
        bool isTopological = true;
        for (int j = 0; j < n; j++){
            v2 = sequence[j];
            for (auto iter = before[v2].begin(); iter != before[v2].end(); iter++){
                if (!visited[*iter]){
                    isTopological = false;
                    result.push_back(i);
                    break;
                }
            }
            if (isTopological)
                visited[v2] = true;
            else
                break;
        }
    }

    // 输出结果
    auto iter = result.begin();
    printf("%d", *iter);
    iter++;
    while (iter != result.end()){
        printf(" %d", *iter);
        iter++;
    }
    printf("\n");

    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!