백준 1976 여행가자 - 2차원 array 형태로 데이터 주어질 때 효과적인 union find

문제 링크

www.acmicpc.net/problem/1976

풀이 아이디어

2차원 배열에 메모리를 할당해서 0과 1을 전부 저장할 필요가 없다.

1이 나올 시에는 두 노드를 가지고 disjoint set을 만드는 것이므로,

바로 union find를 때려 버리면 되는 문제였다.

코드

#include <bits/stdc++.h>
using namespace std;

int n,m;
int node;
int root[201];

int find(int x){
    if(root[x]==x) return x;
    else return root[x]=find(root[x]);
}
void un(int x, int y){
    x = find(x);
    y = find(y);
    root[x]=y;
}
int main(void){
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        root[i]=i;

    for(int i=1; i<=n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> node;
            if(node) un(i,j);
        }
    }
    int b;
    cin>>node;
    b=find(node);
    for(int i=1; i<m; i++){
        cin>>node;
        if(b!=find(node)){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}