집합 문제입니다.
N명의 사람과 M개의 파티가 있을 때 지민이가 과장된 말을 할 수 있는 수를 구해야합니다.
매번 파티에서 사람들을 집합으로 묶어줍니다.
해당 파티에 진실을 아는사람이 있는지 확인합니다.
M번의 파티를 탐색해서 진실을 아는 사람이 속한 집합인지 확인하고
속하지 않은 경우 결과값에 1을 더해주었습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n + 1];
int[] turn = new int[m];
int size;
int num;
int result = 0;
st = new StringTokenizer(br.readLine());
size = Integer.parseInt(st.nextToken());
for (int i = 0; i <= n; ++i) {
arr[i] = i;
}
for (int i = 0; i < size; ++i) {
num = Integer.parseInt(st.nextToken());
arr[num] = 0;
}
for (int i = 0; i < m; ++i) {
st = new StringTokenizer(br.readLine());
size = Integer.parseInt(st.nextToken());
int[] temp = new int[size + 1];
int parent = 100;
for (int j = 1; j <= size; ++j) {
temp[j] = Integer.parseInt(st.nextToken());
parent = Math.min(parent, check(temp[j], arr, false, 0));
}
turn[i] = temp[1];
for (int j = 1; j <= size; ++j) {
check(temp[j], arr, true, parent);
}
}
for (int i = 0; i < m; ++i) {
if (check(turn[i], arr, false, 0) != 0) {
++result;
}
}
bw.write(result + "\n");
bw.close();
}
static public int check(int num, int[] arr, boolean toggle, int change) {
if (num == arr[num] || num == 0) {
if (toggle) {
arr[num] = change;
}
return arr[num];
}
int value = check(arr[num], arr, toggle, change);
arr[num] = value;
return value;
}
}
'알고리즘' 카테고리의 다른 글
[Java] 백준 1253번 좋다 (0) | 2023.07.03 |
---|---|
[Java] 백준 2310번 어드벤처 게임 (0) | 2023.07.01 |
[Java] 백준 2225번 합분해 (0) | 2023.06.29 |
[Java] 백준 5639번 이진 검색 트리 (0) | 2023.06.28 |
[Java] 백준 17404번 RGB거리 2 (0) | 2023.06.27 |