[백준][union find] 1976 여행가자 c++구현

목차

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

문제

 

참고

아래를 참고하고 보면 더 이해가 잘 갈 것이다.

https://be-senior-developer.tistory.com/29

[Union find] c++ 구현 및 설명

 

문제 구현 방향

union find로 구현을 했고 특이점이 있다면 부모를 자식보다 크게 설정함으로써 무한루프에 빠지지 않도록 하였다.

또한 부모를 설정하는 과정에서 트리를 합치는 과정을 넣어야 한다. 

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<map>

using namespace std;


int N;
int M;

int v[1005] = { 0 };
vector<int> target;

int findRoot(int num) {
    int n = v[num];
    if (n == num)
        return n;
    return findRoot(n);
}

void unionRoot(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    if (x != y) {
        if (x > y)
            v[y] = x;
        else
            v[x] = y;
    }
}


int main() {
    cin >> N;
    cin >> M;
    int stand;
    int num;
    for (int i = 0; i < 1004; i++) {
        v[i] = i;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> num;
            if (num) {
                unionRoot(i + 1, j + 1);
                if (i < j)
                    v[i + 1] = j + 1;
                else
                    v[j + 1] = i + 1;
            }
        }
    }
 
    for (int i = 0; i < M; i++) {
        cin >> num;
        if (i == 0){
            stand = findRoot(num);
            continue;
        }
        if(stand != findRoot(num))
        {
            cout << "NO";
            return 0 ;

        }

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