백준 4803번. 트리(c++) / 유니온파인드

dfs로 해결할 수 있는 문제지만, 유니온파인드를 사용해서 풀었다.

다만, 문제를 풀다가 계속 20%에서 틀려서 엄청 고생했다..ㅎㅎ

 

스터디원의 도움을 받아서 반례를 찾을 수 있었다.

간선을 모두 이어서 cycle이 형성되면 그 집단의 최상위 부모를 cycle[최상위부모] = true로 해주었다.

하지만, 문제가 cycle이 이미 형성되고 간선을 긋게 되면 그것을 같은 cycle집단으로 판단하지 못하는 잘못된 로직을 구현했다.

 

아래는 내가 틀렸던 반례이다.

9 9
1 2
2 3
3 4
4 5
3 5
6 7
7 8
6 8
8 9

정답 : Case 1: No trees.

 

// 트리(유니온파인드)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <map>
 
using namespace std;
 
int n, m, a, b;
int connect[555] = {0, };
bool cycle[555];
 
int find(int node)
{
    if(connect[node]==node){
        return node;
    }
 
    return connect[node] = find(connect[node]);
}
 
void setting()
{
    for(int i=1; i<=n; i++){
        connect[i] = i;
        cycle[i] = false;
    }
}
 
int countTree()
{
    map<int, int> m;
    int ans = 0;
    for(int i=1; i<=n; i++){
        int node = find(i);
        if(cycle[node]) continue;
        if(m.count(node)==0){
            m[node] = 1;
            ans++;
        }
    }
 
    return ans;
}
 
int main()
{
    int testcase = 0;
    while(1){
        testcase++;
        cin>>n>>m;
        if(n==0 && m==0) break;
        setting();
        for(int i=0; i<m; i++){
            cin>>a>>b;
            int from = find(a);
            int to = find(b);
 
            if(from!=to){
                if(cycle[from] || cycle[to]){
                    cycle[from] = true;
                    cycle[to] = true;
                }
                connect[from] = to;
            }else{
                cycle[from] = true;
            }
        }
 
        int cnt = countTree();
        if(cnt==0){
            cout<<"Case "<<testcase<<": No trees."<<"\n";
        }else if(cnt==1){
            cout<<"Case "<<testcase<<": There is one tree."<<"\n";
        }else{
            cout<<"Case "<<testcase<<": A forest of "<<cnt<<" trees."<<"\n";
        }
    }
    
    return 0;
}