티스토리 뷰

알고리즘 관련/BOJ

BOJ)7535 A Bug's Life

JASON 자손9319 2017. 3. 22. 14:39

문제: icpc.me/7535


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


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


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


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
#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(* n + 1);
        disc.assign(* n + 10);
        scc.assign(* n + 10);
    }
    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 <= * 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;
}
cs


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

BOJ)1747 소수&팰린드롬  (0) 2017.03.23
BOJ)10835 카드게임  (0) 2017.03.23
BOJ)7535 A Bug's Life  (0) 2017.03.22
BOJ)3747 완벽한 선거!  (0) 2017.03.22
BOJ)8992 집기 게임  (0) 2017.03.20
BOJ)10937 두부 모판 자르기  (1) 2017.03.16
TAG
댓글
댓글쓰기 폼