hades

[Baekjoon] 1043๋ฒˆ: ๊ฑฐ์ง“๋ง ๋ณธ๋ฌธ

๐Ÿ‘Š PS/Algorithm

[Baekjoon] 1043๋ฒˆ: ๊ฑฐ์ง“๋ง

hades1 2024. 8. 1. 20:45

๐Ÿฅ… ๋ฌธ์ œ

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

 

๐Ÿ” ์„ค๊ณ„

ํŒŒํ‹ฐ์— ์ตœ์ข…์ ์œผ๋กœ ์ง„์‹ค์„ ์•Œ๊ฒŒ ๋˜๋Š” ์‚ฌ๋žŒ์ด ํ•œ ๋ช…์ด๋ผ๋„ ์žˆ์œผ๋ฉด, ๊ฑฐ์ง“๋ง์„ ํ•  ์ˆ˜ ์—†๋‹ค.

 

ํŒŒํ‹ฐ์— ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ์„ ๋จผ์ € ์ฐพ๊ณ , ์žˆ์œผ๋ฉด ํŒŒํ‹ฐ์— ์žˆ๋Š” ์‚ฌ๋žŒ๋“ค์„ ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ๋“ค์˜ ์ง‘ํ•ฉ์œผ๋กœ union ํ•˜๋ ค๊ณ  ํ–ˆ๋Š”๋ฐ, ์ด ๋ฐฉ๋ฒ•์€ ํŒŒํ‹ฐ ์ค‘ ๋’ค์— ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ์ด ์žˆ์œผ๋ฉด, ์•ž์— ํŒŒํ‹ฐ์—์„œ๋Š” ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ๋“ค์˜ ์ง‘ํ•ฉ์œผ๋กœ unionํ•  ์ˆ˜ ์—†๋‹ค.

 

๋‹จ์ˆœํ•˜๊ฒŒ ํŒŒํ‹ฐ์— ์žˆ๋Š” ์‚ฌ๋žŒ๋“ค์„ ๋ฌถ๊ธฐ๋งŒ ํ•˜๋ฉด, ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ์ด ๋’ค์ชฝ ํŒŒํ‹ฐ์— ๋‚˜์™€๋„ ๋’ค์ชฝ ํŒŒํ‹ฐ์—์„œ ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ๋“ค์˜ ์ง‘ํ•ฉ์œผ๋กœ ๋ฐ˜์˜๋˜๊ธฐ ๋•Œ๋ฌธ์—, ํŒŒํ‹ฐ ๊ฐ๊ฐ์—์„œ ์ง„์‹ค์„ ์•„๋Š” ์‚ฌ๋žŒ์ด ์—†์œผ๋ฉด ์ด ํŒŒํ‹ฐ ์ˆ˜์—์„œ ๊ฐ์†Œ์‹œํ‚ค๊ธฐ๋งŒ ํ•˜๋ฉด ๋œ๋‹ค.

 

๐Ÿ‘Š ํ’€์ด

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

int n, m, number, person, result = 0;
vector<int> parent(51);
vector<vector<int>> parties;

int find_parent(int x) {
	if (parent[x] != x) {
		return find_parent(parent[x]);
	}
	return x;
}

void union_parent(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	cin >> number;
	if (number == 0) {
		cout << m << "\n";
		return 0;
	}

	for (int i = 0; i < number; i++) {
		cin >> person;
		parent[person] = 0;
	}
	
	for (int i = 0; i < m; i++) {
		vector<int> party;
		cin >> number;
		for (int j = 0; j < number; j++) {
			cin >> person;
			party.push_back(person);
		}
		for (int j = 1; j < number; j++) {
			union_parent(party[0], party[j]);
		}
		parties.push_back(party);
	}

	int result = m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < parties[i].size(); j++) {
			if (find_parent(parties[i][j]) == 0) {
				result -= 1;
				break;
			}
		}
	}
	cout << result << "\n";

	return 0;
}