백준 24391 귀찮은 해강이

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

• 자료 구조, 분리 집합

• 풀이
  연결되어 있는 건물들을 같은 집합에 포함 시킨다.
  그 후 다른 집합에 있는 건물일 시 (check 함수), res를 더하여 마지막에 출력한다.

• 코드

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)

const int MAX = 101010;
int N, M, res=0;
int par[MAX];

void init(int num){
    for(int i=0;i<num;i++) par[i]=i;
}

int find(int x){
    if(x==par[x]) return x;
    return par[x]=find(par[x]);
}

void Union(int x, int y){
    x=find(x); y=find(y);
    if(x<y) par[y]=x;
    else par[x]=y;
}

bool check(int x, int y){
    x=find(x); y=find(y);
    if(x==y) return true;
    return false;
}

int main(void){
    fast;
    cin>>N>>M;
    init(N);
    for(int i=0;i<M;++i){
        int s,e; cin>>s>>e;
        Union(s,e);
    }
    vector<int> table(N);
    for(int i=0;i<N;++i) cin>>table[i];
    for(int i=0;i<N-1;++i){
        if(!check(table[i], table[i+1])) res++;
    }
    cout<<res;
}