백준 1976번 - 여행 가자

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

Disjoint-set문제로 Union-Find 문제라고도 한다.

크루스칼에서 간선을 잇는 두 정점의 집합을 구할 때 사용되기도 하는데

Union-find가 그리디에서만 사용되지는 않기 때문에 그래프 문제로 분류를 했다.

도시를 각 정점이라고 생각했을 때

최초에 입력받는 정점의 최상위 정점을 자신의 인덱스 번호로 지정을 해주었다.

그 다음으로 연결된 두 정점이 주어졌을 때,

인덱스 번호가 작은 정점을, 인덱스 번호가 큰 정점의 부모로 Union을 해준다.

마지막으로 여행 경로를 확인한 후에

이어진 여행 경로의 두 정점(도시)의 최상위 정점을 확인하는 데, 만약 최상위 부모가 다르다면

서로 이어진 경로가 아님을 뜻하기 때문에 NO를 출력해주면 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int N,M;
int map[201][201]={0};
 
vector<int> parent; //도시 별 최상위 도시
vector<int> path; //여행 경로
 
int fn_find(int node){
    
    while(node!=parent[node])
        node=parent[node];
    
    return node;
}
 
void fn_union(int x,int y){
    
    x=fn_find(x);
    y=fn_find(y);
    
    if(x<y) parent[y]=x;
    else    parent[x]=y;
}
 
int main(){
    
    cin>>N>>M;
    
    parent = vector<int> (N+1,0);
    path = vector<int> (M+1,0);
    
    for(int i=1;i<=N;i++)
        parent[i]=i;
    
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            
            scanf("%d",&map[i][j]);
            
            if(map[i][j])
                fn_union(i,j);
        }
    
    
    for(int i=1;i<=M;i++)
        scanf("%d",&path[i]);
    
    
    bool check=true;
    for(int i=1;i<M;i++){
        if(fn_find(path[i])!=fn_find(path[i+1])){
            check=false;
            break;
        }
    }
    
    if(check)   cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
    return 0;
}