By yusijia

Updated:

Contents 
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

//如果要找到所有的拓扑排序，就要使用深度优先搜索的方法来解决

//下面的方法只能找到一个拓扑序列
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>

using namespace std;

const int N = 100;
const int M = 10000;

int n, m, counts;
int head[N];//用来表示以i为起点的第一条边存储的位置实际上你会发现这里的第一条边存储的
//位置其实在以i为起点的所有边的最后输入的那个编号
int in[N];//统计每个点的入度

struct EdgeNode{
    int to;
    int w;
    int next;
};

EdgeNode Edge[M];

void input()
{
    cin >> n >> m;
    int i, j, w;
    memset(head, -1, sizeof(head));
    memset(in, 0, sizeof(in));
    for(int k = 1; k <= m; k++){
        cin >> i >> j;                  //>> w;
        in[j]++;                        //统计每个点的入度
        w = 1;
        Edge[k].to = j;
        Edge[k].w = w;
        Edge[k].next = head[i];
        head[i] = k;//很明显,head[i]保存的是以i为起点的所有边中编号最大的那个
    }//这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性.
}

bool topologicalSort()
{
    int que[100] = {0};
    counts = 0;

    for(int i = 1; i <= n; i++)if(in[i] == 0){
        que[counts++] = i;              //先将图中入读为0的顶点加入队列
    }//删除从该顶点发出的全部有向边，更新in入度数组
    for(int i = 0; i < counts; i++){    //i向后移动，逻辑上删除入度为0的点，存入que数组
        for(int k = head[que[i]]; ~k; k = Edge[k].next){
            in[Edge[k].to]--;
            if(in[Edge[k].to] == 0){
                que[counts++] = Edge[k].to;//如果in[]变为0，说明新的入度为0的顶点被找到，加入队列中
            }
        }
    }
    if(counts != n)
        return false;                   //如果失败说明有环
    for(int i = 0; i < counts; i++)
        cout << que[i] << ' ';          //输出拓扑序列
    cout << endl;
}

int main()
{
    freopen("input.txt", "r", stdin);
    input();
    topologicalSort();
    return 0;
}
/*
输入：
7 12
1 2
1 4
1 3
2 4
2 5
3 6
4 3
4 6
4 7
5 4
5 7
7 6

输出：
1 2 5 4 7 3 6
*/
Contents