[1976] 여행 가자

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

1976번: 여행 가자

같은 도시를 여러 번 방문이 가능하다는 조건에 의해서, "[1717] 집합의 표현"과 거의 동일한 문제가 되었다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

#define union _union

int n, m, p[201];

int find(int cur) {

    if (p[cur] < 0) return cur;

    return p[cur] = find(p[cur]);

}

void union(int A, int B) {

    A = find(A), B = find(B);

    if (A == B) return;

    if (p[A] < p[B])

        p[A] += p[B], p[B] = A;

    else

        p[B] += p[A], p[A] = B;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    memset(p, -1, sizeof(p));

    int i, j;

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++) {

            int x;

            cin >> x;

            if (x == 1) union(i + 1, j + 1);

        }

    }

    vector<int> v(m);

    for (i = 0; i < m; i++) cin >> v[i];

    for (i = 0; i < m; i++) {

        for (j = 0; j < m; j++) {

            if (find(v[i]) != find(v[j])) {

                cout << "NO";

                return 0;

            }

        }

    }

    cout << "YES";

    return 0;

}

---