[백준 9372] 상근이의 여행

사실 이 문제는 알고리즘이 필요가 없다.

 

모든 가중치는 1이라 봐도 무방하고 

모든 국가를 여행하기 위한 비행기 종료의 최소 개수 == 간선 수 이므로

최소신장트리의 간선수는 정점개수 N -1이므로 답이 그냥 N-1이다.

 

---

#include <iostream>
#include <vector>

#define SIZE 1001

using namespace std;

int T, N, M;
vector<pair<int,int>> arr;
int parent[SIZE];

// 최소 스패닝 트리
// 모든 간선의 가중치가 1이므로 정렬필요없음
int findParent(int node) {
	// 자기자신이 부모노드이면
	if (parent[node] == node) return node;
	// 자기자신이 부모노드가 아니면
	// 자신의 부모를 찾고 그걸로 자신의 부모값을 최신화 시켜주면서 반환
	else return parent[node] = findParent(parent[node]);
}

void updateParent(int a,int b) {
	a = findParent(a);
	b = findParent(b);

	if(a!=b) parent[b] = a;
}

bool isCycle(int a, int b) {
	a = findParent(a);
	b = findParent(b);

	return a == b;
}

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

	cin >> T;

	for (int i = 0; i < T; i++) {
		arr.clear();
		
		cin >> N >> M;
		int a, b;
		// 비행기 종류
		for (int k = 0; k < M; k++) {
			cin >> a >> b;
			arr.push_back(make_pair(a, b));
		}

		// parent배열 최신화
		for (int k = 1; k <= N; k++) parent[k] = k;

		// 간선 수
		int cnt = 0;
		for (int k = 0; k < M; k++) {
			a = arr[k].first;
			b = arr[k].second;

			// a와 b가 사이클이 아니면 추가해주기
			if (!isCycle(a, b)) {
				cnt++;
				updateParent(a, b);
			}
		}

		cout << cnt << "\n";
	}

	return 0;
}