백준 20955 민서의 응급 수술(c++)

문제 URL : https://www.acmicpc.net/problem/20955

 

문제 접근법 : union find를 이용하는 문제입니다.

트리의 성질을 아냐모르냐 의문제입니다.

트리는 반드시 n개의 노드에서 n-1개의 간선이 기때문에

이미 같은집합이면 그집합을 또 간선을 추가할 필요가없고

 

같은집합이 아니면 어떤노드는 상관없이 같은집합안에서 어떤노드간에 간선하나만 추가하면 트리가 구성됩니다.

 

소스코드 : 

 

//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
vector<int> parent;
int res = 0;
int find(int idx){
    if(parent[idx]==idx)return idx;
    return parent[idx]=find(parent[idx]);
}
void merge(int a,int b){
    a= find(a);
    b= find(b);
    parent[b]=a;
}
void input(){
    cin>>n>>m;
    parent=vector<int>(n+1);
    for(int i=1;i<=n;i++)parent[i]=i;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        res+=find(a)==find(b);
        if(find(a)!=find(b)){
            merge(a,b);
        }
    }
}

void solve(){
    
    for(int i =1;i<=n;i++){
        if(find(1)!=find(i)){
            merge(find(1),i);
            res++;
        }
    }
    cout<<res<<"\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.