[백준 / C++] 1976번: 여행 가자

백준 1976번: 여행 가자
알고리즘 분류: 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합

백준 문제 바로가기

🤨 Hmm...

분리 집합 복습할 겸 푼 문제다.

여행경로로 계획에 속한 도시들을 모두 방문하기 위해서는 도시들끼리 모두 연결되어 있어야 한다.

그래서 각 도시가 속한 부모가 같으면 모두 연결되어 있는 것임을 이용하여 풀었다.

💻 소스 코드

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#define int long long
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int N, M;
    int parent[201];
public:
    BJ();
    int findParent(int x);
    void unionParent(int x, int y);
};

BJ::BJ() {
    cin >> N >> M;

    int tmp;
    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 >> tmp;
            if (tmp == 1)
                unionParent(i, j);
        }
    }

    vector<int> city;
    int MIN = N;
    for (int i = 0; i < M; i++) {
        cin >> tmp;
        city.emplace_back(tmp);
        MIN = min(MIN, tmp);
    }

    for (int i = 0; i < M; i++) {
        if (findParent(city[i]) != MIN) {
            cout << "NO";
            return;
        }
    }
    cout << "YES";
}
int BJ::findParent(int x) {
    if (parent[x] == x)
        return x;
    parent[x] = findParent(parent[x]);
    return parent[x];
}
void BJ::unionParent(int x, int y) {
    int px = findParent(x);
    int py = findParent(y);
    if (px <= py)
        parent[py] = px;
    else
        parent[px] = py;
}

signed main(){
    fastIO;

    BJ a;
}