https://www.acmicpc.net/problem/17352 > n; for (int i = 0; i > a >> b; unionParent(a, b); } int parent_of_1 = getParent(1); for (int i = 2; i

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 아이디어 분리집합을 알면 날먹 가능한 문제 이 유형이 대체로 티어가 높게 잡혀 날먹하기 좋다 입력받는 두 노드를 merge하기 전 사이클이 생기는지 확인한다. 사이클이 생긴다면 그대로 그때의 iteration(> n >> m; for (int i = 0; i a >> b; if (getParent(a) =..

분리 집합 분리 집합을 이용해 풀었다. 분리 집합의 기본을 연습하고 싶다면 이 문제를 풀어보자 2021.09.28 - [PS/백준] - 백준 1717 (C++) 집합의 표현 백준 1717 (C++) 집합의 표현 크루스칼 알고리즘은 모르는 이에게 설명하기도 쉽고 이해하기도 쉽다. unionParent함수에서 일반적으로 부모노드가 더 큰 쪽에 합치지만 일방적으로 첫번째 파라미터인 변수에 union 했다. 코드 // synodic.tistory.com 시간 비교(BFS vs Union set) 찾아보니 이분탐색 + bfs를 이용한 방법이 많다. 맨 위가 나의 제출인데 굉장히 적은 시간과 메모리가 걸린 것으로 보인다. 처음엔 주어진 집합을 전부 union하고 각각의 비용을 2차원 인접 행렬에 저장한 뒤 입력의 ..

이해 분리 집합으로 풀면 된다. i,j를 union하고 m개의 첫번째와 입력받는 m-1개가 연결되었는지 확인한다. 틀렸습니다 92%에서 계속 틀리길래 한참 고민했는데 디버깅 해보니 아니 나는 무슨... union 해주는 과정에서 Parent를 초기화해서...(왜? 아마 코드 줄이려고 그런 흐린 판단을 했던 것 같다...) 내가 한 실수 이외에도 계속 AC를 못 받는다면 index를 1부터 저장해보는 것도 방법일 수 있다. 질문 검색해보니 그런 케이스가 좀 있는 것 같았다. 코드 #include #include #include using namespace std; using ll = long long; const int MAX = 210; const int INF = 987654321; int n, m; ..

https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 아이디어 union find인데 제거할 때 나오는 비용을 세는 대신, 전부 분리한 다음 분리하지 않을 간선만 이은 채로 union을 전부 돌면 된다. 전부 서로소 집합인 상태에서 끊지 않을 간선을 제외한 노드들(예제에서는 1,2)을 union할때와 이후 답을 찾기위한 union은 같으나 후자에서는 부모노드 확인과정을 거친 후 비용을 곱해서 저장해야 한다. 아이디..

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 크루스칼 알고리즘 문제 조건 도시가 연결되어 있는 단위를 (도시 한 개만 존재하는 단위도 포함) 도시 묶음이라 하자. 이 도시 묶음 하나 당 발전소는 단 한 개가 존재해야 한다. (MST에서) 두 노드가 같은 트리 안에 존재할 수 없다는 건 두 노드의 부모노드가 같다는 뜻이다. 따라서 발전소의 부모노드를 통일시킨다 (union한다) 발전소 중 하나의 노드..

크루스칼 알고리즘은 모르는 이에게 설명하기도 쉽고 이해하기도 쉽다. unionParent함수에서 일반적으로 부모노드가 더 큰 쪽에 합치지만 일방적으로 첫번째 파라미터인 변수에 union 했다. 코드 // Kruskal Algorithm Using Union & Find #include #include using namespace std; using ll = long long; const int MAX = 1e7; int n,m; int Parent[MAX]; // Parent[node] == parent of node int getParent(int n) { if (Parent[n] == n) return n; else return Parent[n] = getParent(Parent[n]); } void..