[BOJ] 1976번: 여행 가자

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

Union Find를 사용하면 쉽게 풀 수 있다.

만약 갈 수 있는 경로라면 find함수를 실행했을 때 반환값이 모두 같을 것이다. 

#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, par[201];

int find(int u) {
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u > v) swap(u, v);
    par[u] = v;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; ++i) par[i] = i;
    for (int i = 0, a; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &a);
            if (a == 1) merge(i, j);
        }
    }

    int a, u, v;
    scanf("%d", &a);
    u = find(a - 1);
    for (int i = 1; i < m; ++i) {
        scanf("%d", &a);
        v = find(a - 1);
        if (u != v) {
            puts("NO");
            return 0;
        }
        u = v;
    }
    puts("YES");
    return 0;
}