백준 9344번: 도로 (C++)

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

9344번: 도로

---

Solved By: MST, Kruskal Algorithm

 

N개의 도시들 사이의 도로를 짓는 데에 필요한 비용들의 합이 최소가 되게끔 합니다.

>> MST를 사용할 수 있습니다.

 

MST가 만들어지는 과정에 p, q가 주어진다면 YES, 아니라면 NO를 출력합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10001
#define pii pair<int, int>
using namespace std;

int T;
int n, m;
int parent[MAX];
vector<pair<pii, int>> edges;

bool cmp(pair<pii, int> a, pair<pii, int> b){
    return a.second < b.second;
}

int getRoot(int node){
    if(node == parent[node]) return node;
    return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga != gb) return true;
    else return false;
}

void unionNodes(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga < gb) parent[gb] = ga;
    else parent[ga] = gb;
}

int main(){
    cin >> T;
    while(T--){
        edges.clear();
        
        int p, q; cin >> n >> m >> p >> q;
        
        for(int i = 1; i <= n; i++) parent[i] = i;
        
        for(int i = 0; i < m; i++){
            int u, v, w; cin >> u >> v >> w;
            edges.push_back({{u, v}, w});
        }
        
        sort(edges.begin(), edges.end(), cmp);
        
        bool flag = 0;
        
        for(int i = 0; i < edges.size(); i++){
            int fst = edges[i].first.first;
            int scd = edges[i].first.second;
            if(find(fst, scd)){
                if((fst == p && scd == q) || (fst == q && scd == p)){
                    flag = 1; break;
                }
                unionNodes(fst, scd);
            }
        }
        
        if(flag == 1) cout << "YES";
        else cout << "NO";
        cout << '\n';
    }
}