백준 01976 - 여행 가자

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

1976번: 여행 가자

 

고려사항

• 유니온 파인드 구현.
• findParent는 반복문으로도 가능.
  while( arr[city] != city ){
       city = arr[city];
  }
• 유니온 함수가 중요!
  조사 중인 두 도시의 부모 도시를 구하고, 값이 더 작은 도시를 루트로 합친다!
  이 때 중요한 것은! 조사 중인 도시의 부모 배열을 수정하는 것이 아니라, ( 해도 되긴하지만 연산 이득이 크지 않음. )
  두 도시의 부모를 구했으면, 해당 부모들의 부모 배열을 고쳐야 한다! ( 그래야 나중에 같은 조상을 두고 있는지  조사가능 )
  
  

 

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

int findParent(int arr[], int city){
    if(arr[city] == city){
        return city;
    }

    return arr[city] = findParent(arr, arr[city]);
}

void unionParent(int arr[], int city1, int city2){
    int parent1 = findParent(arr, city1);
    int parent2 = findParent(arr, city2);

    if(parent1 < parent2){
        arr[parent2] = parent1;
    }else{
        arr[parent1] = parent2;
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int parent[201], load[1000];
    int n, m, isConnect;

    cin>>n>>m;

    for(int i=1;i<=n;++i){
        parent[i] = i;
    }

    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>isConnect;
            if(i <= j && isConnect == 1){
                unionParent(parent, i, j);
            }
        }
    }

    for(int i=0;i<m;++i){
        cin>>load[i];
    }

    for(int i=1;i<m;++i){
        if(findParent(parent, load[i-1]) != findParent(parent, load[i])){
            cout<<"NO\n";
            return 0;
        }
    }

    cout<<"YES\n";
    return 0;
}