티스토리 뷰

알고리즘 관련/BOJ

BOJ)3747 완벽한 선거!

JASON 자손9319 2017. 3. 22. 02:46

문제: icpc.me/3747


문제에서 A||B의 셋이 M개가 주어지고 M개의 모든 셋이 동시에 참이 될 수 있는 지 여부를 묻는 문제이므로 2-SAT 모델링을 통해 문제를 해결할 수 있다.


주어진 조건대로 간선을 연결해준 뒤 2-SAT 모델링을 통하여 참 여부를 판단하여 출력해주면 된다.


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
72
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
struct TwoSAT {
    int n, c, sccc;
    vector<vector<int>> vt;
    vector<int> disc, scc;
    TwoSAT(int n) :n(n) {
        disc.assign(* n + 10);
        scc.assign(* n + 10);
        vt.resize(* n + 1);
        c = 0;
    }
    stack<int> st;
    int dfs(int here) {
        st.push(here);
        disc[here] = ++c;
        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 cvt(int x) {
        if (x <= n)
            return x + n;
        else
            return x - n;
    }
    void addEdge(int x, int y) {
        vt[cvt(x)].push_back(y);
        vt[cvt(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[cvt(i)])
                return false;
        return true;
    }
};
int n, m, x, y;
int main() {
    while (scanf("%d%d"&n, &m) != EOF) {
        TwoSAT tsat(n);
        for (int i = 0; i < m; i++) {
            scanf("%d%d"&x, &y);
            if (x < 0)x = tsat.cvt(-x);
            if (y < 0)y = tsat.cvt(-y);
            tsat.addEdge(x, y);
        }
        printf("%d\n", tsat.isSatisfied() ? 0);
    }
    return 0;
}
cs


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

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
BOJ)11410 칙칙폭폭  (0) 2017.03.15
TAG
댓글
댓글쓰기 폼