백준: Class 6 - 1948(DAG에서 최장경로)

</br> DAG(Directed Acyclic Graph)는 사이클이 없는 방향 그래프다.
원래 최장경로 구하기는 NP문제지만, DAG에서는 위상 정렬로 구할 수 있다.
시작점에서 다음 점까지 최대의 시간이 걸리는 것을 고르는 것이기 때문이다.
</br>

1948: 임계경로

https://www.acmicpc.net/problem/1948

#include <bits/stdc++.h>
#define P pair<int, int>

using namespace std;

vector<P> graph[10001];
vector<P> revgraph[10001];
int ind[10001];
int times[10001];

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

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(c, b));
        revgraph[b].push_back(make_pair(c, a));
        ind[b]++;
    }
    int start, arrival;
    cin >> start >> arrival;

    queue<int> q;
    q.push(start);
    while( q.size() ){
        int now = q.front();
        q.pop();
        for(int j = 0; j < graph[now].size() ; j++){
            int c = graph[now][j].first;
            int nx = graph[now][j].second;
            ind[nx]--;
            times[nx] = max(times[nx], times[now] + c);
            if( ind[nx] == 0 ) q.push(nx);
        }
    }
    cout << times[arrival] << '\n';

    q.push(arrival);
    ind[arrival] = 1;
    int cnt = 0;
    while( q.size() ){
        int now = q.front();
        q.pop();

        if( now == start ) break;

        for(int j = 0; j < revgraph[now].size() ; j++){
            int c = revgraph[now][j].first;
            int nx = revgraph[now][j].second;
            if( times[now] - c == times[nx] ){
                cnt++;
                if( ind[nx] == 0 ){
                    ind[nx] = 1;
                    q.push(nx);
                }
            }
        }
    }
    cout << cnt << '\n';

}

얘는 일단 위상 정렬로 최장 경로의 시간은 구했는데, 그 경로들을 다시 탐색도 해야 한다.
따라서 방향이 반대인 그래프에서 도착->시작으로 탐색을 진행하며, 현재 times[now] - c == times[nx]라면 이 길이 최장 경로이므로 이 쪽으로 탐색을 진행한다.
</br>

---

요새 거들 비하면 간단한 편이라 좋다
</br>