[ BOJ 백준 2606번 - 바이러스 ] 해설 및 코드

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

 

목적

1번 컴퓨터와 연결된 컴퓨터의 개수를 구하자.

 

접근법

1. 아주 많은 접근법이 있지만, Disjoint-set 자료구조를 이용하여 접근했다.

 

 

#include<iostream>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
int n,p[101],size[101];
 
int root(int i){
    while(p[i]!=i)i=p[i];
    return i;
}
 
void combine(int a,int b){
    int ra=root(a),rb=root(b);
    if(ra==rb)return;
    if(size[ra]<size[rb]){
        p[ra]=rb;
        size[rb]+=size[ra];
    }else{
        p[rb]=ra;
        size[ra]+=size[rb];
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    f(i,1,n)p[i]=i,size[i]=1;
    int m;cin>>m;
    while(m--){
        int a,b;cin>>a>>b;
        combine(a,b);
    }
    cout<<size[root(1)]-1;
    
    return 0;
}
 
 
 

 

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

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