[6] [Class 3] - 백준 11724 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

아까 다른 문제를 DFS로 풀어서

이건 그냥 Union find 로 풀어보았다. 

 

// https://www.acmicpc.net/problem/11724
// Connected Component
// Union find 으로 해도 되고, dfs로 해도 되고..

#include <bits/stdc++.h>

using namespace std;

int parent[1001];

int find_parent(int n){
  if(parent[n] == n){
    return n;
  }

  return parent[n] = find_parent(parent[n]);
}

void merge(int b, int c){
  b = find_parent(b);
  c = find_parent(c);

  if(b > c){
    parent[b] = c;
  }
  else {
    parent[c] = b;
  }
}

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  int N,M;
  cin >> N >> M;

  for(int i = 1 ; i <= N ; i++){
    parent[i] = i;
  }

  for(int i = 0 ; i < M ; i++){
    int a,b;
    cin >> a >> b;

    merge(a,b);
  }

  set<int> s;

  for(int i = 1 ; i <= N ; i++){
    s.insert(find_parent(i));
  }

  cout << s.size();

  return 0;
}

 

많이 느리다...