Algorithm - Topological Sort (위상정렬)

개념

어떤 일을 할 때 순서를 찾는 알고리즘이다

Topological Sort

.

---

작동원리

1. InDegree가 0인 정점을 queue에 넣는다.

2. queue에서 pop하고 갈 수 있는 정점들의 InDegree를 감소시키고, InDegree가 0이면 queue에 넣는다.

3. 1 ~ 2를 반복한다.

---

시간복잡도

정렬할 때 BFS를 사용 -> O(V + E)

---

문제

1948 임계경로

www.acmicpc.net/problem/1948

1948번: 임계경로

---

코드

#include <bits/stdc++.h>
using namespace std;

class Edge {
public:
    int vertex, distance;

    explicit Edge(int vertex, int distance) : vertex(vertex), distance(distance) {

    }
};

vector<int> topologicalSort(int n, int begin, int end, vector<int> &inDegree, vector<vector<Edge>> &graph) {
    queue<Edge> que;
    for (int i = 1;i <= n;++i) {
        if (inDegree[i] == 0) {
            que.emplace(i, 0);
        }
    }

    vector<bool> isFromBegin(n + 1);
    isFromBegin[begin] = true;

    vector<int> distance(n + 1);
    while (!que.empty()) {
        Edge now = que.front(); que.pop();

        for (Edge &next : graph[now.vertex]) {
            if (isFromBegin[now.vertex]) {
                distance[next.vertex] = max(distance[next.vertex], now.distance + next.distance);
                isFromBegin[next.vertex] = true;
            }

            inDegree[next.vertex]--;
            if (inDegree[next.vertex] == 0) {
                que.emplace(next.vertex, distance[next.vertex]);
            }
        }
    }

    return distance;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> inDegree(n + 1);
    vector<vector<Edge>> graph(n + 1), rgraph(n + 1);
    while (m--) {
        int v1, v2, distance;
        cin >> v1 >> v2 >> distance;

        inDegree[v2]++;
        graph[v1].emplace_back(v2, distance);
        rgraph[v2].emplace_back(v1, distance);
    }

    int begin, end;
    cin >> begin >> end;

    vector<int> distance = topologicalSort(n, begin, end, inDegree, graph);
    cout << distance[end] << "\n";

    set<pair<int, int>> edges;
    queue<Edge> que;
    vector<bool> isVisited(n + 1);

    que.emplace(end, distance[end]);
    while (!que.empty()) {
        Edge now = que.front(); que.pop();

        if (isVisited[now.vertex]) {
            continue;
        }

        isVisited[now.vertex] = true;
        for (Edge &next : rgraph[now.vertex]) {
            if (!isVisited[next.vertex] && distance[now.vertex] - distance[next.vertex] == next.distance) {
                que.emplace(next.vertex, next.distance);
                edges.emplace(min(now.vertex, next.vertex), max(now.vertex, next.vertex));
            }
        }
    }

    cout << edges.size() << "\n";
}