[BOJ 1939 // C++] 중량제한

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1939번 문제인 중량제한이다.
문제는 아래 링크를 확인하자.

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

1939번: 중량제한

글쓴이는 가장 많은 중량을 버틸 수 있는 다리부터 순서대로 다리를 놓아나가다가 두 공장이 같은 component에 있는 때가 오면 그때 놓은 다리가 버틸 수 있는 중량을 출력하는 것으로 문제를 해결했다.

 

아래는 제출한 소스코드이다.

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

int uf[10001];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

vector<pair<int, pair<int, int>>> edges;

bool comp(pair<int, pair<int, int>> p1, pair<int, pair<int, int>> p2) {
	return p1 > p2;
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) uf[i] = i;
	for (int i = 0; i < M; i++) {
		int x, y, w; cin >> x >> y >> w;
		edges.push_back({ w,{x,y} });
	}

	sort(edges.begin(), edges.end(), comp);

	int A, B; cin >> A >> B;

	for (auto edge : edges) {
		int x = findf(edge.second.first), y = findf(edge.second.second);
		if (x == y) continue;
		uf[y] = x;
		if (findf(A) == findf(B)) {
			cout << edge.first;
			return 0;
		}
	}
}