Algorithm in A..Z - 백준 3648 아이돌

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

3648번: 아이돌

---

접근

Tarjan 알고리즘으로 SCC를 구현하면 특성상 하위의 SCC가 먼저 결정된다. 그렇기 때문에 x < ¬x 를 만족하면 x가 참이된다.

상근이가 합격하려면 ¬x가 False면 합격이기 때문에 그래프를 구현할 때 역방향으로 그래프를 구현하여 ¬x가 False가 될 수 있는지 확인한다. (명제의 대우는 동치이기 때문에 가능하다.)

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int NONE = -1;

int n, m;
vector<vector<int>> graph;

inline int convert(int value) {
    return value <= n ? value + n : value - n;
}

int order;
stack<int> st;
vector<int> sccNumber, isVisited;
vector<vector<int>> scc;
int dfs(int index) {
    st.push(index);
    isVisited[index] = order++;

    int value = isVisited[index];
    for (auto &next : graph[index]) {
        if (isVisited[next] == NONE) {
            value = min(value, dfs(next));
        } else if (sccNumber[next] == NONE) {
            value = min(value, isVisited[next]);
        }
    }

    if (value == isVisited[index]) {
        vector<int> cycle;
        while (!st.empty()) {
            int i = st.top(); st.pop();

            cycle.push_back(i);
            sccNumber[i] = (int)scc.size();
            if (i == index) {
                break;
            }
        }

        scc.push_back(cycle);
    }

    return value;
}

inline void init() {
    graph = vector<vector<int>>(2*n + 1);

    order = 0;
    st = stack<int>();
    sccNumber = isVisited = vector<int>(2*n + 1, NONE);
    scc = vector<vector<int>>();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    while (cin >> n >> m) {
        init();
        while (m--) {
            int s, e;
            cin >> s >> e;

            s = s < 0 ? convert(-s) : s;
            e = e < 0 ? convert(-e) : e;

            graph[convert(s)].push_back(e);
            graph[convert(e)].push_back(s);
        }

        for (int i = 1;i <= 2*n;++i) {
            if (isVisited[i] == NONE) {
                dfs(i);
            }
        }

        bool flag = true;
        for (int i = 1;i <= n;++i) {
            if (sccNumber[i] == sccNumber[convert(i)]) {
                flag = false;
                break;
            }
        }

        if (sccNumber[convert(1)] < sccNumber[1]) {
            flag = false;
        }

        cout << (flag ? "yes" : "no") << "\n";
    }
}