BOJ)7535 A Bug's Life

문제: icpc.me/7535

서로 성별이 다른 두 벌레들의 정보가 주어질 때 vaild한지 여부를 묻는 문제이다.

우리는 두 벌레들의 정보가 들어온다는 걸 이용하여 2-SAT 모델링을 통하여 문제를 해결 할 수 있다.

A와 B가 들어 왔을 때 두 벌레의 성별이 다르다는 걸 (A||B)&&(!A||!B)로 표현해준 뒤 이를 이용하여 2-SAT 모델링을 한 뒤 vaild 여부를 판단해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
struct TwoSAT{
    int n, c, sccc;
    vector<vector<int>> vt;
    vector<int> disc, scc;
    stack<int> st;
    TwoSAT(int n) :n(n) {
        c = sccc = 0;
        vt.resize(2 * n + 1);
        disc.assign(2 * n + 1, 0);
        scc.assign(2 * n + 1, 0);
    }
    int dfs(int here) {
        disc[here] = ++c;
        st.push(here);
        int ret = disc[here];
        for (int i = 0; i < vt[here].size(); i++) {
            int there = vt[here][i];
            if (!disc[there])
                ret = min(ret, dfs(there));
            else if (!scc[there])
                ret = min(ret, disc[there]);
        }
        if (ret == disc[here]) {
            sccc++;
            while (st.size()) {
                int h = st.top();
                st.pop();
                scc[h] = sccc;
                if (h == here)break;
            }
        }
        return ret;
    }
    int convert(int v) {
        if (v <= n)return v + n;
        else return v - n;
    }
    void addEdge(int x, int y) {
        vt[convert(x)].push_back(y);
        vt[convert(y)].push_back(x);
    }
    bool isSatisfied() {
        for (int i = 1; i <= 2 * n; i++)
            if (!disc[i])dfs(i);
        for (int i = 1; i <= n; i++)
            if (scc[i] == scc[convert(i)])return false;
        return true;
    }
};
int t, n, m, x, y, c;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        TwoSAT tsat(n);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &x, &y);
            tsat.addEdge(x, y);
            tsat.addEdge(tsat.convert(x), tsat.convert(y));
        }
        printf("Scenario #%d:\n%suspicious bugs found!\n\n", ++c, tsat.isSatisfied() ? "No s" : "S");
    }
    return 0;
}