[Baekjoon] 2606번: 바이러스 (c++)

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

2606번: 바이러스

 

 

모든 반례를 해봤는데도 계속 틀렸다고나와서 좀 헤맸다 ㅠㅠ

Union Find를 다시 공부하다보니 알게됬는데

 

return parent[x] = Find(parent[x]) 가 아니라

return parent[x]로 해버려서 x의 맨 위 부모(root)를 못찾아서 그런거였다..!

1717번과 비슷하게 Union Find를 사용하면 쉽게 풀 수 있는 문제였다

 

1. 입력받은 a b 연결 (Union)

2. 1과 연결된 컴퓨터를 찾아야하므로(Find) 모든 컴퓨터 i에 대하여 Find(i) == 1 이면 result++

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int parent[101] = {0,};

int Find(int x){
    if(parent[x] == x) return x;
    else {
        return parent[x] = Find(parent[x]);
    }
    
}
void Union(int a, int b){
    
    int x = Find(a);
    int y = Find(b);
    
    if(x > y) parent[x] = y;
    else parent[y] = x;
    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int c, inp, a,b;
    
    cin >> c;
    cin >> inp;
    for(int i=1;i<=c;i++) parent[i] = i;

    while (inp--) {
        cin >> a >> b;
        Union(a, b);

    }
    
    int result = 0;
    for(int i=2;i<=c;i++){
        if( Find(i) == 1) result++;
    }
    
    cout << result;
    return 0;
}