백준/9372/union_find/상근이의 여행

백준/9372/union_find/상근이의 여행

문제 해석

상근이가 가장 적은 종류의 비행기로 모든 나라를 여행 할 수 있게 즉, 루트를 최소로하면서 모든 노드를 방문할 수 있는 방법을 고르는 것이다.

문제 풀이

Disjoint-Set을 활용하면 이미 방문했던 노드를 제외하고 해당 루트를 방문할 수 있다.

풀이

첫번째 풀이

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

vector<int>p(1'001, -1);

queue<pair<int, int>>q;

int find(int num)
{
	if (p[num] == -1)return num;
	return p[num] = find(p[num]);
}

bool union_find(int u, int v)
{
	u = find(u); v = find(v);

	if (u == v)return false;
	else if (u > v) p[u] = v;
	else p[v] = u;
	return true;
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T = 0;

	cin >> T;

	for (int i = 0;i < T;i++)
	{
		// N은 국가의 수 ,M은 비행기의 종류
		int N, M = 0;
		cin >> N >> M;

		for (int j = 0;j < M;j++)
		{
			int a, b = 0;
			cin >> a >> b;
			q.push({ a,b });
		}

		int result = 0;
		while (!q.empty())
		{
			auto cur = q.front(); q.pop();

			if (union_find(cur.first, cur.second))
			{
				result++;
			}
		}

		for (int z = 0;z <= 1000;z++)
		{
			p[z] = -1;
		}

		cout << result << '\n';
	}


	return 0;
}