티스토리 뷰

알고리즘 관련/UVaOJ

UVaOJ)12645 Water Supply

JASON 자손9319 2017. 6. 19. 16:51

문제: 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의 개수를 출력해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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<intint>> 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, 0sizeof(in));
        memset(disc, 0sizeof(disc));
        memset(scc, 0sizeof(scc));
        edge.assign(m + 1, { 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;
}
cs


'알고리즘 관련 > UVaOJ' 카테고리의 다른 글

UVaOJ)12159 Gun Fight  (0) 2017.06.27
UVaOJ)12878 Flowery Trails  (0) 2017.06.23
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19
UVaOJ)11751 Installing Diagnostic Software  (0) 2017.06.19
UVaOJ)12460 Careful teacher  (0) 2017.06.17
댓글
댓글쓰기 폼