www.acmicpc.net/problem/1043

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

이야기의 진실을 아는사람과 같은 파티에 참석하는 사람들에게는 거짓말을 하면 안됩니다.

저는 이를 union-find로 만나는 모든 사람들을 체크해주었습니다.

 

각 파티에 모이는 사람들을 union-find로 같이 묶어주면서

진실을 아는 사람과 모르는 사람이 만날 때 둘 다 진실을 아는 것으로 판단하였습니다.

 

최종으로 M개의 파티를 돌면서 find(x)가 모두 false면 거짓말을 할 수 있고, 아니면 진실만을 얘기해야합니다.

 

 

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int parent[] = new int[51];
    static ArrayList<Integer> list[] = new ArrayList[51];
    static boolean know[] = new boolean[51];
    static int N, M, K;
 
    static int find(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = find(parent[v]);
    }
 
    static void Union(int u, int v) {
        int x = find(u);
        int y = find(v);
 
        parent[y] = x;
        if (know[y]) {
            know[x] = true;
        }
    }
    
    static void func() {
        int ans = 0;
        for (int i = 0; i < M; i++) {
            boolean chk = true;
            for (int j = 0; j < list[i].size(); j++) {
                int x = list[i].get(j);
 
                if (know[find(x)]) {
                    chk = false;
                    break;
                }
            }
 
            if (chk)
                ans++;
        }
        
        System.out.println(ans);
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        init();
 
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < K; i++) {
            x = Integer.parseInt(st.nextToken());
            know[x] = true;
        }
 
        for (int i = 0; i < M; i++) {
            int u = -1, v;
            list[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            for (int j = 0; j < K; j++) {
                v = Integer.parseInt(st.nextToken());
                list[i].add(v);
                if (u == -1) {
                    u = v;
                    continue;
                }
                Union(u, v);
                u = v;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

'algorithm > Union-Find' 카테고리의 다른 글

boj 20040 사이클 게임  (0) 2021.06.27
boj 10775 공항  (0) 2021.03.17
boj 4195 친구 네트워크  (0) 2021.03.17
boj 1976 여행 가자  (0) 2021.03.17
boj 1717 집합의 표현  (0) 2021.02.06

+ Recent posts

티스토리툴바