[BOJ] 2606. 바이러스

#include <iostream>
using namespace std;

int n,m;
int arr[1005][1005];
int cash[1005];
int cnt;

void dfs(int v){
    cash[v] = 1;
    for(int i=1; i<=n; i++){
        if( cash[i] != 1 && arr[v][i] == 1){
            cnt ++;
            dfs(i);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    while (m--) {
        int a,b;
        cin >> a >> b;
        arr[a][b] = arr[b][a] = 1;
    }
    cnt = 0;
    dfs(1);
    
    cout << cnt << endl;
    
    return 0;
}

#include<iostream>
using namespace std;
int p[105];

int Find(int x){
    if(x == p[x])
        return x;
    else{
        int y = Find(p[x]);
        p[x] = y;
        return p[x];
    }
    return x;
}

void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    p[y] = x;
}

int main(){
    for(int i=1; i<=105; i++)
        p[i] = i;

    int n,m;
    cin >> n >> m;
    
    int a, b;
    while (m--) {
        scanf("%d%d", &a, &b);
        Union(a, b);
    }
    
    int ans=0;
    for(int i=1; i<=n; i++)
        if( Find(1) == Find(i) )
            ans ++;
    
    cout << ans-1 << endl;
    return 0;
}