그래프 연결요소 - union find로 찾아야하는 연결요소 문제 1 -

1. 문제 D - Unicyclic Components (atcoder.jp) D - Unicyclic Components AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 주어진 그래프에서 모든 연결요소가 정점의 개수와 간선의 개수가 같은지 판단하는 문제 2. 풀이 연결요소 하니까 BFS로 찾아볼려고 했는데.. 이게 간선을 관리하기가 만만치 않다 심지어 이 문제는 두 정점 사이 간선이 여러개 있어도 상관없고, 동일한 정점에 간선이 있는 루프도 있다 editorial 피셜로 "One can manage the connect..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2023. 3. 14.
  • textsms
컴퓨터로 한붓그리기 하는 방법 - 오일러 경로를 찾는 알고리즘

컴퓨터로 한붓그리기 하는 방법 - 오일러 경로를 찾는 알고리즘

1. 문제 16168번: 퍼레이드 (acmicpc.net) 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 2. 오일러 경로(eulerian trail) "모든 변을 단 한번만 지나서 주어진 그래프를 완성할 수 있는가" 그래프의 모든 간선을 1번만 지나서 모든 정점을 방문하는 연속된 경로를 오일러 경로라고 부른다 혹은 한붓그리기라고도 불린다. 위와 같이 정점은 여러번 지나도 상관없다 위와 같은 그래프는 오일러 경로가 존재하는 그래프이다. 특히 시작점과 끝점이 같은 오일러 경로는 ..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2023. 2. 19.
  • 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