[6543] 그래프의 싱크

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

6543번: 그래프의 싱크

<문제>

SCC만들어서, outdegree가 0인 정점을 출력하면 된다.

코드에는 ind[]로 되어있는데...변수명을 수정하지 않아서 그렇다. 

SCC로 DAG만들어서 위상정렬하는 테크닉이 적용되다 만(?) 문제들이 몇개 있는거같다.

위상정렬을 절반만 구현하는 듯한 느낌인데, 이 문제는 위상정렬에서 큐에 넣는 부분까지만 구현해주면 충분하다.

 

<소스코드>

 
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, d[100001], SN, sn[100001];
bool checked[100001];
vector<int> adj[100001];
vector<vector<int>> scc;
stack<int> s;
int dfs(int cur) {
    d[cur] = ++cnt;
    s.push(cur);
    int res = d[cur];
    for (int next : adj[cur]) {
        if (d[next] == 0)
            res = min(dfs(next), res);
        else if (!checked[next])
            res = min(res, d[next]);
    }
    if (res == d[cur]) {
        vector<int> temp;
        while (1) {
            int x = s.top();
            s.pop();
            temp.push_back(x);
            checked[x] = true;
            sn[x] = SN;
            if (x == cur) break;
        }
        sort(temp.begin(), temp.end());
        scc.push_back(temp);
        SN++;
    }
    return res;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (1) {
        cin >> n;
        if (n == 0) break;
        m = cnt = SN = 0;
        memset(d, 0, sizeof(d));
        memset(sn, 0, sizeof(sn));
        memset(checked, 0, sizeof(checked));
        int i;
        for (i = 0; i <= 100000; i++) adj[i].clear();
        scc.clear();
 
        cin >> m;
        for (i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            adj[x - 1].push_back(y - 1);
        }
        for (i = 0; i < n; i++)
            if (d[i] == 0) dfs(i);
        sort(scc.begin(), scc.end());
        int ind[100001] = {0};
        for (i = 0; i < n; i++)
            for (int j : adj[i])
                if (sn[i] != sn[j]) ind[sn[i]]++;
        for (i = 0; i < n; i++)
            if (ind[sn[i]] == 0) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}