[ BOJ 백준 1976번 - 여행 가자 ] 해설 및 코드

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

목적

도시가 서로 연결되어 있는지 구하자.

 

접근법

1. 분리집합 기본 문제.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int a[201];
 
int root(int i) {
    while (i != a[i])a[i] = a[a[i]], i = a[i];
    return i;
}
 
void connect(int i, int j) {
    i = root(i), j = root(j);
    if (i != j)a[i] = j;
}
 
bool valid(int m) {
    int tmp; cin >> tmp;
    int r = root(tmp);
    while (--m) {
        cin >> tmp;
        if (r != root(tmp)) {
            while (--m)cin >> tmp;
            return false;
        }
    }
    return true;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    f(i, 1, n)a[i] = i;
    f(i, 1, n)f(j, 1, n) {
        int tmp; cin >> tmp;
        if (tmp)connect(i, j);
    }
    cout << (valid(m) ? "YES" : "NO") << '\n';
 
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.