유니온 파인드 - 거짓말쟁이가 되긴 싫어

<문제>

백준 - 1043: 여행 계획 짜기

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

1043번: 거짓말

<문제 접근>

진실을 알고있는 사람들을 먼저 union 진행한 후, 각 파티에 나오는 사람들도 첫 번째 사람을 기준으로 union한다. 그리고나서 거짓말을 할 수 있는 사람들만 모인 파티를 세준다. 여기서 첫 번째 사람을 기준으로 union을 해야지 문제에 쉽게 접근할 수 있다.

<슈도 코드>

→ cnt 세는 코드는 전체 코드와 다름 

<전체 코드>

#include <iostream>
#include <vector>
using namespace std;
static vector <int> v;

void Union(int f, int s);
int find(int n);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector <int> t_g;
	vector <vector<int>> n;

	int human, party, t, t_p, num, num_human, cnt = 0;
	cin >> human >> party;
	cin >> t;
	
	v.resize(human + 1, 0);
	t_g.resize(t + 1, 0);

	for (int i = 1; i <= human; i++) {
		v[i] = i;
	}

	if (t == 0) {
		cout << party;
		return 0;
	}
	else { 
		for (int i = 1; i <= t; i++) {
			cin >> t_p;
			t_g[i] = t_p;
		}
		
		int k = t_g[1];
		
		for (int i = 1; i <= t; i++) {
			Union(k, t_g[i]);
		}
		
		n.resize(party + 1);

		for (int i = 1; i <= party; i++) { // --> O(n^2)
			cin >> num;

			for (int j = 0; j < num; j++) {
				cin >> num_human;
				n[i].push_back(num_human);
			}
			
			for (int j = 0; j < num; j++) {
				Union(n[i][0], n[i][j]); // --> 시간 복잡도 상수
			
		}
		
		for (int i = 1; i <= party; i++) { // --> O(n^2)
			for (int j = 0; j < n[i].size(); i++) {
				if (find(k) != find(n[i][j])) {
					cnt += 1;
				}
				if (i == party) {
					break;
				}
			}
		}
		
		cout << cnt;
		return 0;
		
	}
	
}

void Union(int f, int s) {
	if (f > s) {
		int tmp = f;
		f = s;
		s = tmp;
	}
	int f_find = find(f);
	int s_find = find(s);
	v[s_find] = f_find;
}

int find(int n) {
	if (n == v[n]) {
		return n;
	}
	else {
		return v[n] = find(v[n]);
	}
}