[백준][C++]11724번 연결 요소의 개수

코딩테스트/백준

[백준][C++]11724번 연결 요소의 개수

윤깡패 2023. 9. 16. 13:46

문제

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

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어

www.acmicpc.net

풀이

유니온 파인드(Union-Find) 알고리즘

유니온 파인드(Union-Find) 알고리즘 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 + 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 유니온 파인드 알고리즘 핵심 이론 union 연

soobin0821.tistory.com

코드

#include <iostream>
#include <vector>
using namespace std;

void union_parent(int a, int b);
int find_parent(int a);
static vector<int> parent;

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

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

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

  for(int i = 0; i < M; i++)
  {
    int u, v;
    cin >> u >> v;
    union_parent(u, v);
  }

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

  cout << count;	// 연결 요소 개수 출력
  
  return 0;
}

void union_parent(int a, int b)
{
  a = find_parent(a);
  b = find_parent(b);

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

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

728x90