백준 1043번 - 거짓말(C++)

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

 처음 봤을 땐 브루트포스로 전부 확인하는 형식으로 풀었는데 3%에서 틀렸습니다가 발생했다.

그래프 문제라고는 상상을 못했다. 정확히는 유니온 파인드 문제였다. 유니온 파인드 알고리즘은 정확히 공부한 적이 없는데 이번에 공부할 수 있었다.

 

1. 먼저 각 진실을 알고 있는 자들의 유니온(집합) 번호를 0번으로 지정한다.

2. 파티를 열고 파티를 들어온 1번 사람들과 이후 사람들을 합쳐준다.

3. 이후 각 파티를 다시 돌며 몇개의 파티에서 과장이 가능한지 체크한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int N, M, K;
int root[51];

int u_find(int x) {
	if (root[x] == x) return x;
	else return root[x] = u_find(root[x]);
}
void Union(int x, int y) {
	int rootx = u_find(x);
	int rooty = u_find(y);

	if (rootx != rooty) {
		if (rootx < rooty)
			root[rooty] = rootx;
		else
			root[rootx] = rooty;
	}
}



int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		root[i] = i;
	}
	
	cin >> K;

	for (int i = 0; i < K; i++) {
		int tmp;
		cin >> tmp;
		root[tmp] = 0;
	}

	int party[51][51];
	int partyNum[51];

	for (int i = 0; i < M; i++) {
		cin >> partyNum[i];
		cin >> party[i][0];
		//cout << party[i][0] << endl;
		for (int j = 1; j < partyNum[i]; j++) {
			cin >> party[i][j];
			Union(party[i][0], party[i][j]);
		}
	}

	int answer = M;

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < partyNum[i]; j++) {
			//cout << party[i][j] << " " << u_find(root[party[i][j]]) << endl;
			if (u_find(root[party[i][j]]) == 0) {
				answer--;
				break;
			}
		}
	}

	cout << answer << '\n';
}