대표자가 같으면 union하지 말아야한다 (union by rank 주의점)

https://atcoder.jp/contests/abc420/tasks/abc420_e E - Reachability QueryAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n개의 정점과 0개의 간선이 주어진다. 각 정점은 1번부터 n번까지 번호가 있고, 처음에 모든 정점은 흰색이다. q개의 쿼리가 주어지는데 각 쿼리는 3종류중 하나이다. 1) u와 v를 무방향 간선으로 연결 2) v가 흰색이면 검은색으로 바꾸고 검은색이면 흰색으로 바꿈 3) 정점 v에서 검은색 정점에 0개 이상의 간선을 타고 도달할 수 있는지 검사한다..

  • format_list_bulleted 알고리즘/분리집합
  • · 2025. 8. 27.
  • textsms

union find 재활훈련 - union by size 복기하기

1. 문제1 4143번: Bridges and Tunnels (acmicpc.net) 4143번: Bridges and Tunnels The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the total number of bridges or tunnels built. This number will be no more than 100,000. We assume that al www.acmicpc.net 2. 풀이1 서로 연결되는 간선이 주어질때마다 각 노드의 집합 크기를 구하는 문제 find..

  • format_list_bulleted 알고리즘/분리집합
  • · 2023. 1. 31.
  • textsms

union find 응용문제 풀어보면서 분리집합 개념 재활하기

1. 문제 16562번: 친구비 (acmicpc.net) 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 2. 풀이 어렵게 생각하지 말고.. 먼저 union find 함수를 작성하자 먼저 parent를 찾는 find함수 def find_parent(x,parent): if x != parent[x]: parent[x] = find_parent(parent[x],parent) return parent[x] 다음 union을 수행하는 함수 def ..

  • format_list_bulleted 알고리즘/분리집합
  • · 2023. 1. 9.
  • textsms

union find 최적화 - union by size 배우기

1. 문제 4195번: 친구 네트워크 (acmicpc.net) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구관계인 간선이 주어질때마다 각 사람(노드)에 속한 집합의 크기를 구하는 문제 2. 풀이 이 문제가 어렵게 느껴지는 이유는 일단 노드 수가 주어지지 않는다.. 간선의 수 f만 주어지는데.. 이럴 경우 최대 노드 수는 2f개 일 것이다. 사실 최대 노드 수만 알아도 문제를 푸는데 상관이 없다. 왜냐하면 union이 일어날때마다 각 노드에 속한 집합의 크기만 구하면 되니까 parent = [..

  • format_list_bulleted 알고리즘/분리집합
  • · 2022. 10. 5.
  • textsms
union find 알고리즘 최적화 -경로압축과 rank union-

union find 알고리즘 최적화 -경로압축과 rank union-

1. 기본 union find 알고리즘의 문제점 기본적인 union find 알고리즘을 사용할 경우 union을 수행하면.. 예를 들어 최악의 경우 위와 같은 union이 형성될 수 있다. 1의 대표자를 찾을 때, 2번, 3번, 4번을 확인하고 나서야 5번을 확인하여 1의 대표자가 5이구나 라는 것을 알 수 있다 이렇게 구성되는 경우 노드의 개수가 v개이고 간선의 개수가 m개이면 최악의 경우 O(VM)이라는 비효율적인 알고리즘이 된다. 특히 모든 1,2,3,4,5의 루트 노드가 5번인데 굳이 하나씩 거슬러 올라가서 전부 확인해야하나? union 그래프가 위와 같이 구성된다면, 2,3,4의 루트 노드는 단 1번만 5를 검사하면 바로 알 수 있으므로 효율적이다. 2. 경로압축(path compression)..

  • format_list_bulleted 알고리즘/분리집합
  • · 2022. 9. 29.
  • textsms
union find 알고리즘 활용 - 사이클을 판별하는 방법 -

union find 알고리즘 활용 - 사이클을 판별하는 방법 -

1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에서의 간선으로 표현될 수 있는데(두 노드를 합치므로) 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로 사이클을 판별할 수 있다. 2. 알고리즘 2-1) 각 간선을 확인하면서 두 노드의 루트 노드를 확인 2-1-1) 루트 노드가 서로 다르다면, 두 노드에 대해 union 연산을 수행 2-1-2) 루트 노드가 서로 같다면 사이클이 발생 2-2) 그래프에 포함된 모든 간선에 대해 위 과정을 반복 3. 예시로 이해하는 사이클 판별 알고리즘 3-1) 초기 단계에서는 모든 노드에 ..

  • format_list_bulleted 알고리즘/분리집합
  • · 2022. 9. 29.
  • textsms