백준 1976 (C++) 여행 가자 (틀렸습니다, 까닭)

이해

분리 집합으로 풀면 된다.

i,j를 union하고

m개의 첫번째와 입력받는 m-1개가 연결되었는지 확인한다.

 

 

틀렸습니다

92%에서 계속 틀리길래 한참 고민했는데

디버깅 해보니 아니 나는 무슨...

union 해주는 과정에서 Parent를 초기화해서...(왜? 아마 코드 줄이려고 그런 흐린 판단을 했던 것 같다...)

내가 한 실수 이외에도 계속 AC를 못 받는다면

index를 1부터 저장해보는 것도 방법일 수 있다. 질문 검색해보니 그런 케이스가 좀 있는 것 같았다.

 

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int MAX = 210;
const int INF = 987654321;
int n, m;
int Parent[MAX]; // Parent[node] == parent of node
int getParent(int n1) {
    if (Parent[n1] == n1) return n1;
    else return Parent[n1] = getParent(Parent[n1]);
}
void unionParent(int n1, int n2) {
    n1 = getParent(n1);
    n2 = getParent(n2);
    if (n1 != n2) {
        Parent[n2] = n1;
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        Parent[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int a;
            cin >> a;
            if (a == 1) {
                unionParent(i, j);
            }
        }
    }
    int s,e;
    cin >> s;
    for (int i = 0; i < m-1; i++) {
        cin >> e;
        if (getParent(s) != getParent(e)) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    
    return 0;
}

 

 

 

 

 

 

 

저번에 부산 놀러가서 또 놓쳤다. ㅜㅠㅠㅠㅠㅠ