algorithm/topologicalkahn.cpp at master · phanthaiduong22/algorithm · GitHub

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
#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int V, E;
struct option
{
    bool operator()(const int &a, const int &b) const
    {
        return a > b;
    }
};

bool topologicalsort(vector<vector<int>> &graph, vector<int> &result)
{
    vector<int> indegree(V+1, 0);
    priority_queue<int, vector<int>, option> zero_indegree;
    for (int u = 0; u < V; u++)
    {
        vector<int>::iterator it;
        for (it = graph[u].begin(); it != graph[u].end(); it++)
            indegree[*it]++;
    }
    for (int i = 0; i < V; i++)
        if (indegree[i] == 0)
        {
            zero_indegree.push(i);
        }
    while (!zero_indegree.empty())
    {
        int u = zero_indegree.top();
        zero_indegree.pop();
        result.push_back(u);
        vector<int>::iterator it;
        for (it = graph[u].begin(); it != graph[u].end(); it++)
        {
            indegree[*it]--;
            if (indegree[*it] == 0)
            {
                zero_indegree.push(*it);
            }
        }
    }
    for (int i = 0; i < V; i++)
    {
        if (indegree[i] != 0)
            return false;
    }
    return true;
}
int main()
{
    freopen("topologicalkahn.inp", "r", stdin);
    freopen("topologicalkahn.out", "w", stdout);
    vector<vector<int>> graph;
    vector<int> result;

    cin >> V >> E;
    graph.assign(V + 1, vector<int>());
    for (int u, v, i = 0; i < E; i++)
    {
        cin >> u >> v;
        graph[u-1].push_back(v-1);
    }
    if (topologicalsort(graph, result) == true)
    {
        for (int i = 0; i < result.size(); i++)
            cout << result[i]+1 << " ";
    }
    else
        cout << "Sandro fails.";
}