백준 1976번 여행 가자 — 유니온 파인드 C++ 풀이

#include <iostream>

using namespace std;

int cityCount, planCityCount, isLinked;
int parents[201];

int find_parent(int x) {
    if (parents[x] == x) return x;
    return parents[x] = find_parent(parents[x]);
}

void set_union(int a, int b) {
    a = find_parent(a);
    b = find_parent(b);
    if (a > b) parents[a] = b;
    else parents[b] = a;
}

bool same_set(int a, int b) {
    return find_parent(a) == find_parent(b);
}

int main() {
    for (int i = 0; i < 201; i++) parents[i] = i;

    cin >> cityCount >> planCityCount;

    for (int i = 1; i <= cityCount; i++) {
        for (int j = 1; j <= cityCount; j++) {
            cin >> isLinked;
            if (isLinked) set_union(i, j);
        }
    }

    int connectionCount = 1;
    int prevCity, currentCity;

    cin >> prevCity;

    for (int i = 1; i < planCityCount; i++) {
        cin >> currentCity;
        if (same_set(prevCity, currentCity)) {
            connectionCount++;
            prevCity = currentCity;
        }
    }

    cout << (connectionCount == planCityCount ? "YES" : "NO");

    return 0;
}