UVaOJ)12645 Water Supply

문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393

오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다.

이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다.

즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int n, m, x, y, in[1010], r, disc[1010], scc[1010], sccc, c;
vector<vector<int>> vt;
vector<pair<int, int>> edge;
vector<vector<int>> svt;
stack<int> st;
int dfs(int here) {
    disc[here] = ++c;
    int ret = disc[here];
    st.push(here);
    for (auto next : vt[here]) {
        if (!disc[next])
            ret = min(ret, dfs(next));
        else if (!scc[next])
            ret = min(ret, disc[next]);
    }
    if (ret == disc[here]) {
        sccc++;
        while (1) {
            int h = st.top();
            st.pop();
            scc[h] = sccc;
            if (h == here)break;
        }
    }
    return ret;
}
int main(){
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(in, 0, sizeof(in));
        memset(disc, 0, sizeof(disc));
        memset(scc, 0, sizeof(scc));
        edge.assign(m + 1, { 0,0 });
        vt.clear();
        vt.resize(n + 1);
        c = sccc = r = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &edge[i].first, &edge[i].second);
            vt[edge[i].first].push_back(edge[i].second);
        }
        for (int i = 0; i <= n; i++)
            if (!disc[i])dfs(i);
        for (int i = 0; i < m; i++) {
            if (scc[edge[i].first] == scc[edge[i].second])continue;
            in[scc[edge[i].second]]++;
        }
        for (int i = 1; i <= sccc; i++)
            if (i != scc[0] && !in[i])r++;
        printf("%d\n", r);
    }
    return 0;
}