Union Find

https://m.blog.naver.com/fbfbf1/222278788809

유니온 파인드(Union Find) c++

원래 바킹독 강의를 보면서 공부하려고 했는데 나오기까지 한참 남았길래 독학했습니다.

---

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

1717번: 집합의 표현

유니온 파인드를 구현하는 문제였습니다.

구현할 때, ran[v]++에 주의합시다.

ran[u]++로 할 경우, 루트가 아닌 노드의 ran을 증가시키므로 최적화가 되지 않습니다.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int parent[100'0003];
int ran[100'0003];

//경로압축으로 최적화
int find(int u){ //find
    if(parent[u]==u) return u;
    return parent[u] = find(parent[u]);
}

//rank로 최적화
void merge(int u, int v){ //union
    u = find(u); //집합의 대표를 가리키게 함
    v = find(v); //집합의 대표를 가리키게 함
    if(u==v) return; //이미 속해있으면 return;
    if(ran[u]>ran[v]) swap(u,v); //길이가 긴 트리에 짧은 트리를 붙여서 트리의 높이를 최대한 일정하게 함
    parent[u]=v; //v가 속한 집합의 대표를 u가 속한 집합의 대표에 붙임
    if(ran[u]==ran[v]) ran[v]++; //길이 같은 트리가 붙으면 길이가 1 늘어남.
}

void init(){
    for(int i=0;i<=n;i++){
        parent[i]=i;
        ran[i]=1;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    init();
    while(m--){
        int q,a,b; cin>>q>>a>>b;
        if(q==0){ //merge
            merge(a,b);
        }
        if(q==1){ //find
            (find(a)==find(b)) ? cout<<"YES\n" : cout<<"NO\n";
        }
    }
    return 0;
}

---

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

16562번: 친구비

유니온 파인드 최적화를 위해 rank 배열을 쓰면 a 배열과 겹치지 않을까 걱정했는데, 그냥 rank를 사용하지 않으면 됐습니다. 

굳이 필요 없다고 느껴지면 경로 압축을 제외한 최적화는 사용하지 않아도 될 것 같습니다.

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int a[10'003];
int parent[10'003];
vector<bool> chk(10'003,false);

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    if(a[v]>a[u]) swap(u,v);
    parent[u]=v;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    while(m--){
        int u,v; cin>>u>>v;
        merge(u,v);
    }

    int cost=0;
    for(int i=1;i<=n;i++){
        if(parent[i]==i) cost+=a[i];
    }
    if(cost<=k) cout<<cost;
    else cout<<"Oh no";
    return 0;
}

---

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

1976번: 여행 가자

union find 재밌네요...

#include<bits/stdc++.h>
using namespace std;

int ran[1003];
int parent[1003];
int n,m;

void init(){
    for(int i=0;i<=m;i++){
        parent[i]=i;
        ran[i]=1;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]); 
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    if(ran[u]>ran[v]) swap(u,v);
    parent[u]=v;
    if(ran[u]==ran[v]) ran[u]++;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    init();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x; cin>>x;
            if(x==1) merge(i,j);
        }
    }

    m--;
    int pre, nxt; cin>>pre;
    while(m--){
        cin>>nxt;
        if(find(pre)!=find(nxt)){cout<<"NO"; return 0;}
        swap(pre,nxt);
    }
    cout<<"YES";
    return 0;
}

---

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

20040번: 사이클 게임

사이클이 생겼다는 말은, union find에서 두 원소를 union하는데, 이미 같은 집합에 속해 있는 경우입니다.

bool 변수를 추가해 해결했습니다.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int parent[500'003];
int ran[500'003];
bool hasCycle=false;

void init(){
    for(int i=0;i<=n;i++){
        parent[i]=i;
        ran[i]=1;
    }
}

int find(int u){
    if(u==parent[u]) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) {hasCycle=true; return;}
    if(ran[u]>ran[v]) swap(u,v);
    parent[u]=v;
    if(ran[u]==ran[v]) ran[v]++;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        merge(u,v);
        if(hasCycle){
            cout<<i;
            break;
        }
    }
    if(!hasCycle) cout<<0;
    return 0;
}

---

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

4195번: 친구 네트워크

스스로 풀긴 했는데, 대충 때려맞췄다.

map으로 string을 int로 매핑했고, len 배열로 해당 집합에 속한 원소의 수를 관리했다.

실수로 질문 게시판을 보다가 u==v인 경우에도 출력을 해줘야 한다는 것을 미리 봐서 아쉽다.

배열의 크기는 친구 관계의 수가 최대 10만개가 들어오므로, 서로 다른 두 친구가 10만번 들어올 경우 20만개의 이름이 M에 담기기에, 그에 맞게 다른 배열들의 크기도 20만으로 잡았다.

#include<bits/stdc++.h>
using namespace std;

map<string,int> M; //이름을 숫자로 매핑
int parent[200'003];
int rnk[200'003];
int len[200'003]; //len[n] n을 루트로 하는 집합에 속한 원소의 갯수

int find(int u){
    if(parent[u]==u) return u;
    return parent[u]=find(parent[u]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) {cout<<len[v]<<'\n'; return;}
    if(rnk[u]>rnk[v]) swap(u,v);
    parent[u]=v;
    if(rnk[u]==rnk[v]) rnk[v]++;
    len[v]+=len[u];
    cout<<len[v]<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while(t--){
        M.clear();
        for(int i=1;i<=200002;i++){
            parent[i]=i;
            rnk[i]=1;
            len[i]=1;
        }
        int f; cin>>f;
        int idx=0;
        while(f--){
            string uu,vv; cin>>uu>>vv;
            if(M[uu]==0) M[uu]=M.size();
            if(M[vv]==0) M[vv]=M.size();
            int u=M[uu]; int v=M[vv];
            merge(u,v);
        }
    }
    return 0;
}