[ BOJ 백준 4803번 - 트리 ] 해설 및 코드

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

 

목적

트리(사이클이 없는 연결요소)의 개수를 구하자.

 

접근법

1. disjoint-set 자료구조를 이용하여 트리를 형성하며 사이클 존재여부를 확인한다.

 

2. 주의할 점

• 노드쌍의 번호가 같은 것이 입력으로 주어지는 경우도 고려하자.
• m이 0인 경우

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int n,m,p[501],size[501],chk[501];
 
int root(int i){
    while(p[i]!=i){
        p[i]=p[p[i]];
        i=p[i];
    }
    return i;
}
 
void connect(int a,int b){
    int ra=root(a),rb=root(b);
    if(ra==rb) chk[ra]=0;
    else{
        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); cout.tie(0); cin.tie(0);
    int tc=0;
    while(cin>>n>>m&&n){
        f(i,1,n)p[i]=i,size[i]=1,chk[i]=1;
        
        while(m--){
            int a,b;cin>>a>>b;
            if(a!=b)connect(a,b);
        }
        
        int ans=0;
        f(i,1,n){
            int ri=root(i);
            if(chk[ri])chk[ri]=0,++ans;
        }
        
        cout<<"Case "<<++tc<<": ";
        if(ans==0)cout<<"No trees.\n";
        else if(ans==1)cout<<"There is one tree.\n";
        else cout<<"A forest of "<<ans<<" trees.\n";
    }
    return 0;
}
 

 

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

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