[BOJ 1976] 여행 가자(C++)

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

1976번: 여행 가자

#include <bits/stdc++.h>

using namespace std;
int parents[201];

int find(int i){    //find parents
    if (parents[i]==i){
        return i;
    }
    else{
        return parents[i]=find(parents[i]);
    }
}

void union_(int a, int b){      //make a group
    int pa=find(a);
    int pb=find(b);
    parents[pb]=pa;
}

int main(){
    int N, M, c;
    cin>>N>>M;
    int plans[M];
    bool isImpossible=false;
    for (int i=1; i<=N; i++){
        parents[i]=i;
    }
    for (int i=1; i<=N; i++){
        for (int j=1; j<=N; j++){
            cin>>c;
            if (c==1){
                union_(i,j);        //연결되면 같은 그룹으로 합친다
            }
        }
    }
    for (int i=0; i<M; i++){
        cin>>c;
        plans[i]=c;
    }
    for (int i=0; i<M-1; i++){
        if (find(plans[i])!=find(plans[i+1])){
            isImpossible=true;
            break;
        }
    }
    if (isImpossible){
        cout<<"NO"<<"\n";
    }
    else{
        cout<<"YES"<<"\n";
    }
    return 0;

}

union-find 문제

 

연결되어있으면, union 시켜서 같은 그룹으로 만든다. 

 

갈 수 있는지를 체크하는 것은 두 city가 서로 연결되었는지 체크하면 된다. 이때 같은 그룹(같은 부모를 가진 cities)인지 체크하는 Find 함수를 쓰면 된다.