1976 여행 가자

길이 양방향이라 A->B로 가는게 가능하다면 B->A도 무조건 가능하다.

유니온파인드(disjoint set), bfs, dfs 모두 다 가능하다.

<유니온파인드>

#include <stdio.h>
 
int v[201], c[1001], n, m, t, i, j, fl;
 
int f(int x) {
    return x == v[x] ? x : v[x] = f(v[x]);
}
 
void u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x != y) 
        v[y] = x;
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) v[i] = i;
    for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) {
        scanf("%d", &t);
        if (t) u(i, j);
    }
    for (i = 0; i < m; i++) scanf("%d", &c[i]);
    for (i = 1; i < m && !fl; i++) if (f(c[i]) != f(c[i - 1])) fl = 1;
    printf(fl ? "NO" : "YES");
    return 0;
}

<bfs>

#include <stdio.h>
#include <queue>
using namespace std;
 
int v[201], a[201][201], c[1001], n, m, t, i, j, fl;
bool ch[201];
 
void bfs(int s) {
    queue<int> q;
    q.push(s);
    ch[s] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (!a[x][i] || ch[i]) continue;
            ch[i] = 1;
            q.push(i);
        }
    }
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) v[i] = i;
    for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) scanf("%d", &a[i][j]);
    for (i = 0; i < m; i++) scanf("%d", &c[i]);
    bfs(c[0]);
    for (int i = 1; i < m && !fl; i++) if (!ch[c[i]]) fl = 1;
    printf(fl ? "NO" : "YES");
    return 0;
}

<dfs>

#include <stdio.h>
 
int c[1001], n, m, t, fl;
bool ch[201], a[201][201];
 
void dfs(int s) {
    ch[s] = 1;
    for (int i = 1; i <= n; i++) if (a[s][i] && !ch[i]) ch[i] = 1, dfs(i);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
    for (int i = 0; i < m; i++) scanf("%d", &c[i]);
    dfs(c[0]);
    for (int i = 1; i < m && !fl; i++) if (!ch[c[i]]) fl = 1;
    printf(fl ? "NO" : "YES");
    return 0;
}