Problem Solving►UVa

UVa 10305 - Ordering Tasks

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

找出做事情的順序，事情有一定的相依關係，如:在做 B 之前，必須先完成 A。
p.s. 答案可能不是唯一解。

Solution

關於 拓撲排序

直接邊做拓撲排序邊印出即可。

Code

UVa 10305UVa 10305 - Ordering Tasks
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
62
63
64
65
66
67
68
69
70
71

#include<cstdio>
#include<deque>
#define N 101
using namespace std;

deque<int> DQ[N];
void topo(int n);
int main()
{
    int n, i, j;
    while (scanf("%d", &n) && n)
    {
        for (i = 1; i <= n; i++)
            DQ[i].clear();

        int m, a, b;
        scanf("%d", &m);
        for (j = 0; j < m; j++)
        {
            scanf("%d%d", &a, &b);
            DQ[a].push_back(b);
        }

        topo(n);
    }

    return 0;
}
void topo(int n)
{
    int ref[N] = {}, i;
    //計算每個點，有幾個指向他
    for (i = 1; i <= n; i++)
        for (int j : DQ[i])
            ref[j]++;

    deque<int> Q;
    //將沒有被指的放進 queue ，也就是可以先做的事
    for (i = 1; i <= n; i++)
    {
        if (!ref[i])
            Q.push_back(i);
    }

    bool first = true;
    while (!Q.empty())
    {
        if (!first)
            putchar(' ');
        else
            first = false;

        int s = Q.front();
        Q.pop_front();

        ref[s] = -1;
        printf("%d", s);
        //將 s 所指的點都減 1
        for (int j : DQ[s])
        {
            ref[j]--;
            if (!ref[j])
                Q.push_back(j);
        }

    }

    putchar('\n');
}