[백준/BOJ] 백준 1765번 : 닭싸움 팀 정하기

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

1765번: 닭싸움 팀 정하기

vector<int> enemy[1001]에 해당 학생의 원수들을 저장하고, 1번 학생부터 n번 학생까지 확인하며 해당 학생의 원수를 찾고 그 원수의 원수를 찾아서 해당 학생과 유니온 하고, 친구관계를 유니온 하는 방법으로 유니온 파인드를 진행했다.

 

코드

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

int n;
int m;
vector<int> parent(1001);
vector<int> rank_size(1001, 1);
vector<int> enemy[1001]; //해당 학생의 원수를 저장한다
set<int> check;

void Pre()
{
	for (int i = 1; i <= 1000; i++)
		parent[i] = i;
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}
}

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

	Pre();

	cin >> n;
	cin >> m;

	vector<pair<int, int>> enemy_r;
	vector<pair<int, int>> friend_r;

	for (int i = 0; i < m; i++)
	{
		char r;
		int p, q;

		cin >> r >> p >> q;

		if (r == 'F')
		{
			friend_r.push_back(make_pair(p, q));
		}

		else
		{
			enemy_r.push_back(make_pair(p, q));
		}
	}

	for (int i = 0; i < enemy_r.size(); i++)
	{
		int p = enemy_r[i].first;
		int q = enemy_r[i].second;

		enemy[p].push_back(q);
		enemy[q].push_back(p);
	}

	for (int i = 1; i <= n; i++)
	{
		//i번 학생의 원수가 없을때
		if (enemy[i].size() == 0)
			continue;

		for (int j = 0; j < enemy[i].size(); j++)
		{
			int u = enemy[i][j]; //i번 학생의 원수

			for (int k = 0; k < enemy[u].size(); k++)
			{
				int v = enemy[u][k]; //i번 학생의 원수의 원수

				Merge(i, v);
			}
		}
	}

	for (int i = 0; i < friend_r.size(); i++)
	{
		int u = friend_r[i].first;
		int v = friend_r[i].second;

		Merge(u, v);
	}

	for (int i = 1; i <= n; i++)
	{
		check.insert(parent[i]);

	}

	cout << check.size();

	return 0;
}