* 1. 총 인원 수 만큼 boolean형 배열을 만듦 (전부 false)
* 2. 그 중 진실을아는사람은 true로 변경
* 3. 모든 파티를 돌면서, 해당 파티에 true인 인원이 있으면, 해당 파티의 모든 인원을 true로 변경
* 4. 모든 파티를 돌면서, 해당 파티에 true인 인원이 없으면, count++
* 5. count 출력
import java.io.*;
import java.util.*;
public class no1043 {
private static int people;
private static int partys;
private static int known;
private static int cnt = 0;
private static boolean[] knowns;
private static boolean[][] partyTable;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 번째 줄 : 사람의 수와 파티의 수
StringTokenizer firstLine = new StringTokenizer(br.readLine(), " ");
people = Integer.parseInt(firstLine.nextToken());
partys = Integer.parseInt(firstLine.nextToken());
knowns = new boolean[people+1];
// 두 번째 줄 : 진실을 아는 사람 수, 만약 있으면 진실을 아는 사람 수만큼 리스트에 추가
StringTokenizer secondLine = new StringTokenizer(br.readLine(), " ");
known = Integer.parseInt(secondLine.nextToken());
for(int i=0; i<known ; i++) knowns[Integer.parseInt(secondLine.nextToken())] = true;
partyTable = new boolean[partys][people+1];
//
for(int i=0 ; i<partys ; i++) {
StringTokenizer partyLine = new StringTokenizer(br.readLine(), " ");
// 각 파티당 참석 인원수
int partyMember = Integer.parseInt(partyLine.nextToken());
// 만약 이번 파티에 진실을 아는 사람이 있는 경우 true 체크하여 이번 파티에 모인 사람들을 전부 진실을 알게 해주기위함
boolean check = false;
// 각 파티당 멤버가 누구였는지 체크
for(int j=0 ; j<partyMember ; j++) {
int nowMember = Integer.parseInt(partyLine.nextToken());
partyTable[i][nowMember] = true;
if(knowns[nowMember]) check = true;
}
// 이번 파티에 진실을 아는 사람이 있을 경우, 참석자 전원 진실을 알게됨
if(check) {
for(int j=1 ; j<=people ; j++) {
if(partyTable[i][j]) knowns[j] = true;
}
}
}
// 각 파티 테이블을 돌면서, 해당 파티의 참석자 전원이 진실을 모를 경우 cnt++
for(int i=0 ; i<partys ; i++) {
for(int j=1 ; j<=people ; j++) {
if(partyTable[i][j] && knowns[j]) break; // j번의 사람이 참석했고, 진실을 알 경우 이 파티는 조진거
if(j==people) cnt++; // 끝까지 확인해봤는데 아무도 모르면 야부리 터는거
}
}
System.out.println(cnt);
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int[] truth = new int[51];
int truthNum = sc.nextInt();
for (int i = 0; i < truthNum; i++) {
truth[i] = sc.nextInt();
}
List<Integer>[] party = new ArrayList[m];
for (int i = 0; i < m; i++) {
party[i] = new ArrayList<>();
int num = sc.nextInt();
for (int j = 0; j < num; j++) {
party[i].add(sc.nextInt());
}
}
for (int i = 0; i < m; i++) {
List<Integer> p = party[i];
for (int j = 0; j < p.size(); j++) {
int a = p.get(j);
for (int k = j + 1; k < p.size(); k++) {
int b = p.get(k);
int pa = find(parent, a);
int pb = find(parent, b);
if (pa != pb) {
parent[pb] = pa;
}
}
}
}
int count = 0;
for (int i = 0; i < m; i++) {
List<Integer> p = party[i];
boolean flag = true;
for (int j = 0; j < p.size(); j++) {
int a = p.get(j);
if (Arrays.binarySearch(truth, 0, truthNum, find(parent, a)) >= 0) {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
System.out.println(count);
}
public static int find(int[] parent, int x) {
if (parent[x] == x) {
return x;
}
parent[x] = find(parent, parent[x]);
return parent[x];
}
}
레퍼런스 코드
import java.io.*;
import java.util.*;
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int knowNum = Integer.parseInt(st.nextToken());
boolean[] knowPeople;
//진실을 아는 사람이 없다면 파티의 수를 출력하고 바로 종료
if(knowNum == 0){
System.out.println(M);
return;
}
//자신과 연결된 루트 노드를 설정
parent = new int[N+1];
for(int i = 1; i<=N; i++)
parent[i] = i;
//진실을 아는 사람들의 배열을 생성
knowPeople = new boolean[N+1];
for(int i = 0; i<knowNum; i++) {
int num = Integer.parseInt(st.nextToken());
knowPeople[num] = true;
}
//파티마다 참여한 사람들의 목록을 생성
List<List<Integer>> partyList = new ArrayList<>();
for(int i = 0; i<M; i++)
partyList.add(new ArrayList<>());
for(int i = 0; i<M; i++){
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
for(int j = 0; j<num; j++) {
partyList.get(i).add(Integer.parseInt(st.nextToken()));
//같이 파티에 참가한 사람을 확인
if(j != 0){
int nowIdx = partyList.get(i).get(j);
int exIdx = partyList.get(i).get(j-1);
union(exIdx, nowIdx);
}
}
}
boolean[] visited = new boolean[N+1];
for(int i = 1; i<=N; i++){
if(knowPeople[i] && !visited[i]) {
int root = find(i);
for (int j = 1; j <= N; j++) {
if(find(j) == root){
knowPeople[j] = true;
visited[j] = true;
}
}
}
}
//파티에 진실을 아는 사람이 있는지 확인
boolean[] goParty = new boolean[M];
for(int i = 0; i<M; i++)
goParty[i] = true;
for(int i = 0; i<M; i++){
for(int j = 1; j<=N; j++){
if(knowPeople[j]){
if(partyList.get(i).contains(j))
goParty[i] = false;
}
}
}
int sum = 0;
for(int i = 0; i<M; i++)
if(goParty[i])
sum++;
System.out.println(sum);
}
//자신과 연결된 노드의 루트 노드를 탐색
static int find(int idx){
if(parent[idx] == idx)
return idx;
else {
parent[idx] = find(parent[idx]);
return parent[idx];
}
}
//연결된 노드가 다르다면 연결해줌
static void union(int idx1, int idx2){
int parent1 = find(idx1);
int parent2 = find(idx2);
if(parent1 != parent2)
parent[parent2] = parent1;
}
}