백준 1976 여행 가자 - C++

문제 설명

문제 풀이

이번 문제는 간단한 분리집합 문제로, Union-find를 사용하면 아주 쉽게 풀 수 있는 문제이다. 먼저 각 노드의 부모를 자기 자신으로 초기화를 해준 다음 I와 J의 관계가 1인 노드들을 Union 해준다.
그 이후 여행 계획 노드를 입력받고 그 노드들의 부모가 동일하다면 true, 그렇지 않다면 false를 출력한다.

코드

#include <iostream>

using namespace std;

int n;
int b;
int map[201];
int parent[201];

int getparent(int a)
{
    if (parent[a] == a)
        return a;
    return parent[a] = getparent(parent[a]);
}

void unionparent(int a,int b)
{
    a = getparent(a);
    b = getparent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

bool findparent(int a,int b)
{
    a = getparent(a);
    b = getparent(b);
    if (a == b) return 1;
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> n >> b;
    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 >> t;
            if (t == 1)
                unionparent(i,j);
        }
    }
    int a;
    cin >> a;
    for (int i = 2; i <= b; i++)
    {
        int d;
        cin >> d;
        if (!findparent(a,d))
        {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}