under-graduate.baekjoon/11280.cpp at main · KWONDU/under-graduate.baekjoon · GitHub

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
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAX = 10000 * 2 + 1;

int N, M, xi, xj;
vector<int> v[MAX];

bool visit[MAX];
int scc[MAX], scc_num;
vector<int> v_re[MAX];
stack<int> st;

void dfs1 (int cur) {
    visit[cur] = true;
    for (int nxt : v[cur])
        if (!visit[nxt]) dfs1(nxt);
    st.push(cur);

    return ;
}

void dfs2 (int cur) {
    scc[cur] = scc_num;
    for (int nxt : v_re[cur])
        if (scc[nxt] == 0) dfs2(nxt);

    return ;
}

int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    while (M--) {
        cin >> xi >> xj;
        v[-xi + N].push_back(xj + N);
        v[-xj + N].push_back(xi + N);

        v_re[xj + N].push_back(-xi + N);
        v_re[xi + N].push_back(-xj + N);
    }

    for (int i = 0; i < N * 2 + 1; i++) visit[i] = false;
    for (int i = 0; i < N * 2 + 1; i++) scc[i] = 0;
    scc_num = 0;

    for (int i = 0; i < N * 2 + 1; i++)
        if (!visit[i]) dfs1(i);

    while (!st.empty()) {
        int cur = st.top();
        st.pop();
        if (scc[cur] == 0) {
            scc_num++;
            dfs2(cur);
        }
    }

    int flag = 1;
    for (int i = 0; i < N; i++)
        if (scc[i] == scc[N * 2 - i]) {
            flag = 0;
            break;
        }

    cout << flag;

    return 0;
}