[ 백준 ] 9344번 - 도로 (C++)

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

9344번: 도로

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받아 arr 배열에 저장합니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, map 자료 구조에 이어진 노드들을 저장합니다.

 

3. p 노드와 q 노드가 연결되어 있다면 YES를 출력하고, 아니라면 NO를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<map>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.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()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N, M, p, q;
        scanf("%d %d %d %d", &N, &M, &p, &q);
 
        //visited.clear();
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &arr[i].u, &arr[i].v, &arr[i].w);
        }
 
        sort(arr, arr + M, cmp);
 
        for (int i = 0; i < M; i++) {
            const int u = arr[i].u;
            const int v = arr[i].v;
            const int w = arr[i].w;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                visited[{u, v}] = true;
            }
        }
 
        if (visited[{p, q}] || visited[{q, p}]) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
}