그래프의 싱크

백준 6543번: 그래프의 싱크

아이디어

outdegree가 0인 scc에 속하는 모든 노드를 구하고, 오름차순으로 정렬 후 출력하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 5001;
int cnt, scnt;
int discovered[MAX], sccn[MAX];
bool finished[MAX];
stack<int> s;

int dfs(int cur, vector<vector<int>>& adj, vector<vector<int>>& scc) {
    s.push(cur);
    discovered[cur] = ++cnt;
    int ret = discovered[cur];
    for (int next : adj[cur]) {
        if (!discovered[next]) {
            ret = min(ret, dfs(next, adj, scc));
        }
        else if (!finished[next]) {
            ret = min(ret, discovered[next]);
        }
    }
    if (ret == discovered[cur]) {
        vector<int> v;
        while (1) {
            int t = s.top();
            s.pop();
            v.push_back(t);
            finished[t] = true;
            sccn[t] = scnt;
            if (t == cur) break;
        }
        scc.push_back(v);
        scnt++;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while (1) {
        int n, m;
        cin >> n;
        if (!n) break;
        cin >> m;
        vector<vector<int>> adj(n+1), scc;
        while (m--) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
        }
        memset(discovered, 0, sizeof(discovered));
        memset(finished, 0, sizeof(finished));
        cnt = 0;
        scnt = 0;
        for (int i = 1; i < n+1; i++) {
            if (!discovered[i]) dfs(i, adj, scc);
        }

        vector<vector<int>> sccadj(scc.size());
        vector<int> outdegree(scc.size());
        for (int i = 1; i < n+1; i++) {
            for (int next : adj[i]) {
                if (sccn[i] != sccn[next]) {
                    sccadj[sccn[i]].push_back(sccn[next]);
                    outdegree[sccn[i]]++;
                }
            }
        }

        vector<int> ans;
        for (int i = 0; i < scc.size(); i++) {
            if (!outdegree[i]) {
                for (int x : scc[i]) {
                    ans.push_back(x);
                }
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << ' ';
        }
        cout << '\n';
    }

    return 0;
}

여담

그것이.. 싱크니까..!