문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 같은 그룹의 원소를 찾을 수 있는 Union Find 알고리즘을 사용하면 된다.
  • 각 엣지를 받을 때 마다 두 노드를 Union 시켜준다.
  • 여기서 원소의 parent가 0인 친구의 개수가 Connected Component의 개수이다.

코드

#include <cstdio>

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int ans, n, m, u, v, par[1001];

int find(int a){
    if(par[a] == 0)return a;
    return find(par[a]);
}

void Union(int a, int b){
    int A = find(a), B = find(b);
    if(A == B)return;
    par[A] = B;
}

int main(){
    n = readInt(), m = readInt();
    while(m--){
        u = readInt(), v = readInt();
        Union(u, v);
    }
    for(int i = 1; i < n + 1; i++){
        if(par[i] == 0)ans ++;
    }
    printf("%d", ans);

}

느낀점

  • Union Find를 안보고 이정도 구현했다는 사실에 대단히 만족한다 ㅎㅎ
  • 다음에도 자신있게 풀 수 있을 것 같다.