백준 1976번 여행 가자 C++

출처 : https://www.acmicpc.net/problem/1976

 

연결되어있는 경로를 유니온 파인드를 이용해서 저장하고 여행 계획에 속한 도시들이 전부 이어져있으면 YES, 아니면 NO를 출력했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

vector<int> parent;
vector<int> height;

int GetParent(int n) {
    if (n == parent[n])
        return n;
    return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {
    u = parent[u];
    v = parent[v];

    if (GetParent(u) == GetParent(v))
        return;

    if (height[u] > height[v])
        ::swap(u, v);

    parent[u] = v;

    if (height[u] == height[v])
        height[v]++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    parent = vector<int>(n + 1);
    height = vector<int>(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int input;
            cin >> input;
            if (input == 0) continue;
            if (GetParent(i) == GetParent(j)) continue;
            Merge(i, j);
        }
    }

    set<int> s;
    for (int i = 0; i < m; i++) {
        int input;
        cin >> input;
        int parent = GetParent(input);
        s.insert(parent);
    }

    if (s.size() == 1) cout << "YES";
    else cout << "NO";
}