[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;
}

 

많이 느리다...