1976 여행가자

BOJ::1976 여행가자

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

디스조인트셋을 이용하여, 서로 연결되어있는지 확인하며 풀었다.

#include <stdio.h>
using namespace std;
 
int group[201];
 
int Find(int x) {
    if (group[x] == x) return x;
    return group[x] = Find(group[x]);
}
 
void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    group[b] = a;
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    //서로소집합 초기화
    for (int i = 1; i <= n; i++) {
        group[i] = i;
    }
 
    // 연결되어 있으면 합집합
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            scanf("%d", &x);
            if (x == 1) {
                if (Find(i) != Find(j)) {
                    Union(i, j);
                }
            }
        }
    }
    
    int k;
    scanf("%d", &k);
    k = Find(k);
    for (int i = 1; i < m; i++) {
        int x;
        scanf("%d", &x);
        // 연결되어있지 않으면 NO 출력
        if (k != Find(x)) {
            printf("NO\n");
            return 0;
        }
    }
    //모두 연결되어 있으면 YES 출력
    printf("YES\n");
}