BOJ 3648 아이돌

개요

BOJ 3648 아이돌

• 백준 온라인 저지 3648번 문제
• BOJ 44단계

C++

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

const int MAX = 4001; // 2000 * 2 + 1
vector<int> adj[MAX], revAdj[MAX];
bool visited[MAX];
int sccId[MAX];
stack<int> st;
int n, m;

void addEdge(int a, int b) {
    adj[a].push_back(b);
    revAdj[b].push_back(a);
}

void dfs(int here) {
    visited[here] = true;
    for (int there : adj[here]) {
        if (!visited[there]) dfs(there);
    }
    st.push(here);
}

void reverseDfs(int here, int id) {
    visited[here] = true;
    sccId[here] = id;
    for (int there : revAdj[here]) {
        if (!visited[there]) reverseDfs(there, id);
    }
}

int notVar(int var) {
    return var > n ? var - n : var + n;
}

void solve() {
    // Forward DFS
    fill(visited, visited + MAX, false);
    for (int i = 1; i <= n * 2; i++) {
        if (!visited[i]) dfs(i);
    }

    // Backward DFS
    fill(visited, visited + MAX, false);
    int id = 0;
    while (!st.empty()) {
        int here = st.top();
        st.pop();
        if (!visited[here]) reverseDfs(here, ++id);
    }

    // Check for contradictions
    for (int i = 1; i <= n; i++) {
        if (sccId[i] == sccId[notVar(i)]) {
            cout << "no\n";
            return;
        }
    }
    cout << "yes\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> m) {
        for (int i = 1; i <= n * 2; i++) {
            adj[i].clear();
            revAdj[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            if (a < 0) a = -a + n;
            if (b < 0) b = -b + n;
            addEdge(notVar(a), b);
            addEdge(notVar(b), a);
        }

        // 상근이(1번 참가자)는 반드시 진출해야 함
        addEdge(notVar(1), 1);
        solve();
    }
}