도로 (feat. 백준, 9344번)

도로
https://www.acmicpc.net/problem/9344

9344번: 도로

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
struct node{
	int u, v, w;
};
bool cmp(const node& v1, const node& v2){
	return v1.w < v2.w;
}
node arr[20000];
int vect[10001];
map<pair<int, int>, bool> visited;
int Find(int num){
	if (vect[num] == num) return num;
	return vect[num] = Find(vect[num]);
}
void Union(int a, int b){
	int pa = Find(a);
	int pb = Find(b);
	vect[pb] = pa;
}
int main(){
	register int T;
    cin >> T;
    for(register int t = 0, N, M, p, q; t < T; ++t){
        cin >> N >> M >> p >> q;
		for (register int n = 1; n <= N; ++n)
			vect[n] = n;
        for(register int m = 0; m < M; ++m)
            cin >> arr[m].u >> arr[m].v >> arr[m].w;
		sort(arr, arr + M, cmp);
        for(register int m = 0; m < M; ++m){
			auto& u = arr[m].u;
			auto& v = arr[m].v;
			auto& w = arr[m].w;
			if (Find(u) != Find(v))
				Union(u, v),  visited[{u, v}] = true;
		}
		if (visited[{p, q}] || visited[{q, p}])
            cout << "YES";
		else
            cout << "NO";
        cout << '\n';
	}
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 크루스칼 알고리즘을 사용하였습니다.

MST에서 p와 q에 해당되는 w와의 값을 비교하면 됩니다.