티스토리 뷰

알고리즘 관련/BOJ

BOJ)3682 동치 증명

JASON 자손9319 2017. 1. 31. 18:07

문제: icpc.me/3682


그래프에서 동치임을 증명하기 위해 사용하는 함축의 수의 최솟값을 출력하는 문제이다.


우리는 동치임을 증명하기 위해서 그래프의 사이클을 생성해주면 된다.


우리는 그래프의 SCC를 분류한 뒤 다시 SCC들을 정점으로 가지는 그래프로 압축하여 각 SCC의 indegree와 outdegree의 수를 구해준 뒤 


indegree가 0인 정점과 outdegree가 0인 정점중 최댓값을 출력해주면 된다.


그래프의 사이클을 만들어야 하기 때문에 사이클이 존재하려면 indegree와 outdegree가 적어도 1씩 존재해야 하기 때문이다.


단 그래프가 하나의 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#define MAX_N 20000
using namespace std;
int t, n, m, disc[MAX_N + 1], in[MAX_N + 1], out[MAX_N + 1], x, y, c, s, scc[MAX_N + 1], r[2];
vector<vector<int>> vt;
vector<vector<int>> svt;
stack<int> st;
int dfs(int here) {
    disc[here] = ++c;
    st.push(here);
    int ret = disc[here];
    for (int there : vt[here]) {
        if (!disc[there])
            ret = min(ret, dfs(there));
        else if (!scc[there])
            ret = min(ret, disc[there]);
    }
    if (ret == disc[here]) {
        s++;
        while (1) {
            x = st.top();
            scc[x] = s;
            st.pop();
            if (x == here)break;
        }
    }
    return ret;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d"&n, &m);
        r[0= r[1= c = s = 0;
        vt.clear();
        svt.clear();
        vt.resize(n + 1);
        svt.resize(n + 1);
        memset(scc, 0sizeof(scc));
        memset(in, 0sizeof(in));
        memset(out, 0sizeof(out));
        memset(disc, 0sizeof(disc));
        for (int i = 0; i < m; i++) {
            scanf("%d%d"&x, &y);
            vt[x].push_back(y);
        }
        for (int i = 1; i <= n; i++) {
            if (!disc[i])
                dfs(i);
        }
        for (int i = 1; i <= n; i++) {
            for (int j : vt[i]) {
                if (scc[i] != scc[j])
                    svt[scc[i]].push_back(scc[j]);
            }
        }
        for (int i = 1; i <= s; i++) {
            for (int j : svt[i]) {
                in[j]++;
                out[i]++;
            }
        }
        for (int i = 1; i <= s; i++) {
            r[0+= !in[i];
            r[1+= !out[i];
        }
        if (s == 1)
            printf("0\n");
        else
            printf("%d\n", max(r[0], r[1]));
    }
    return 0;
}
cs


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

BOJ)4354 문자열 제곱  (0) 2017.02.01
BOJ)2233 사과나무  (0) 2017.02.01
BOJ)3682 동치 증명  (0) 2017.01.31
BOJ)11338 XOR Sum  (0) 2017.01.31
BOJ)2211 네트워크 복구  (0) 2017.01.26
BOJ)2275 트리의 높이 줄이기  (0) 2017.01.25
댓글
댓글쓰기 폼