본문 바로가기

disjoint-set

BOJ)5542 JOI 국가의 행사 문제: icpc.me/5542 쿼리에서 받는 두 도시간의 경로 중 경로에 포함 된 도시들의 축제하는 도시와의 떨어진 거리의 값들 중 최솟값이 최대가 되는 경로를 구하는 문제이다. 우선 다익스트라 알고리즘을 사용하여 각 정점들의 가중치(축제가 열리는 도시와의 최단거리)를 구해줄 수 있다. 이후 쿼리를 처리해주어야 하는데 disjoint set을 이용하여 쿼리를 처리해주려고 한다. 우선 각 쿼리 번호에 해당되는 양 끝 정점들에 쿼리 번호들을 저장해준 뒤 간선의 가중치가 큰 순서대로 간선을 정렬하여 간선을 보면서 정점을 dsu를 이용하여 병합해 줄것이다. 이 때 만약 두 정점이 같은 쿼리 번호를 가지고 있다면 해당 쿼리 번호의 답은 그 간선의 가중치가 될 것이다. 1234567891011121314151617.. 더보기
BOJ)10637 Minimum Spanning Tree 문제: icpc.me/10637 간선들의 셋이 주어진다. 출력해야하는 답은 각 간선마다 자신을 제외한 간선들로 만들 수 있는 MST의 가중치의 합을 출력하는 문제이다. 이건 MST에 포함 안되는 간선에 대한 답은 MST의 가중치가 되겠지만 아닌 경우가 문제가 된다. 그렇다면 아닌 경우에 대해 생각해보자. 만약에 MST에 포함되지 않는 간선이 u-v 를 연결한다고 생각해보자 그러면 우리는 mst에서 u v를 잇는 경로상의 어떤 간선을 지워도 이 간선을 통하여 MST를 유지 할 수 있다. 즉 이러한 사실을 이용하여 MST를 만들 때 사용되지 않은 간선들을 가중치 순서대로 정렬하여 오프라인으로 미리 mst상에 사용 된 간선들의 답을 정해주는 것이다. 여기서 매번 경로를 확인해준다면 당연히 TLE를 보게 될 것.. 더보기
UVaOJ)12460 Careful teacher 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3891 문제를 간략하게 설명하면 사전에 존재하는 단어들이 주어진 뒤 쿼리가 들어올 때 쿼리에서 들어오는 두 단어를 A와 B라고할 때 A를 B로 바꿀 수 있는지 여부를 물어보는 문제이다. 이 때 A를 B로 바꾸는 경우는 한글자 씩 바꿀 수 있으며 단, 한글자를 바꾼 단어도 사전에 존재하여야만 바꿀 수 있다. 이 문제는 사전에 존재하는 단어들을 정점으로 생각하고 1글자 다른 단어들을 간선으로 묶어주면 A와 B가 같은 컴포넌트에 존재하는지 여부를 묻는 문제로 변형된다. 이는 disjoint-set을 통하여 해결해줄 수 있다. N제한이 20000이지만 시간.. 더보기
BOJ)2610 회의준비 문제: icpc.me/2610 각각의 컴포넌트에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들의 최댓값이 최소가 되는 정점들을 출력하는 문제이다. 각 정점들간의 최단거리는 플로이드 워셜을 이용하여 구해주면 되고 어떤 컴포넌트에 속한 정점에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들 중 최댓값을 힙에 저장하여 순서대로 답에 넣어주는 것으로 문제를 해결할 수 있다. 힙을 볼 때 이미 처리한 컴포넌트에 속한 정점은 지나쳐주어야하는데 이는 disjoint-set을 이용하면 간단하게 해결해줄 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859.. 더보기
BOJ)6091 핑크 플로이드 문제: icpc.me/6091 플로이드 워셜로 구해진 최단거리의 셋이 주어질 때 원래의 트리에 연결 된 간선만 출력하는 문제이다. 우리는 주어진 최단거리의 셋중에서 가장 작은 간선부터 그리디하게 선택할 수 있다. 근데 이 때 선택하면 안되는 간선을 트리의 성질을 이용하여 알 수 있다. 트리에서 a에서 b로 가는 경로는 유일해야 하므로 내가 현재 보고 있는 간선에 연결 된 양쪽 두 정점이 이미 하나의 컴포넌트를 이루고 있다면 그 간선은 사용하면 안된다. 따라서 우리는 가장 작은 간선부터 연결해 주되 disjoint-set을 이용하여 두 컴포넌트를 연결시켜주어 해당 간선이 컴포넌트를 이루는지 여부를 판단한다. 1234567891011121314151617181920212223242526272829303132.. 더보기
BOJ)10216 Count Circle Groups 문제: icpc.me/10216 N개의 진영이 주어 질 때 각 진영이 통신영역이 닿거나 겹치는 부분이 있으면 서로 통신이 가능하다. 그리고 직접적으로 통신이 불가능 하더라도 중간에 몇개의 통신을 거쳐서 통신이 가능하다면 i와 j는 통신이 가능하다고 본다. 통신이 서로 가능한 진영들을 그룹으로 묶을 때 그룹의 수를 출력하는 문제이다. 우리는 a와b가 통신이 가능하고 b와c가 통신이 가능하면 a와c가 통신이 가능한 그룹이 된다는 사실을 가지고 disjoint set을 통하여 문제를 해결할 수 있다. N이 3000밖에 되지 않으므로 N^2의 방법으로 각 진영들을 비교하여 같은 그룹이 아닌 그룹들중에서 통신영역이 겹치는 두 그룹을 union 시켜주면서 시켜줄때마다 그룹의 수를 하나씩 차감시키는 방법으로 답을 구.. 더보기
BOJ)4195 친구 네트워크 문제 : icpc.me/4195 친구 관계가 생길 때 마다 가입한 두사람의 친구 네트워크에 몇명이 있는지 구하는 문제이다. 문제의 답은 union_find를 통하여 쉽게 구해줄 수 있지만 string으로 들어오는 입력 때문에 좌표 압축이나 map을 이용한 테크닉이 필요하다. -좌표압축 이용123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #include #include #include #include using namespace std;int par[200010];int t, n;int num[200010];vect.. 더보기
BOJ)10775 공항 문제: icpc.me/10775 비행기가 도착하는 순서대로 게이트에 도킹을 하는데 한 게이트에는 오직 한대의 비행기만 도킹이 가능하다 이때 각각의 비행기는 1~g번째 게이트중 하나에 도킹할 수 있다는 정보가 들어올 때 최대로 도킹할 수 있는 비행기의 수를 출력하면 된다. g번째 게이트부터 도킹을 하는게 이득인 것임은 자명하므로 disjoint-set을 이용하여 g게이트에 도킹이 될 경우 다시 g게이트를 확인 할 때 g-1게이트를 확인 하도록 parent를 설정해주면 된다. 만약 find 호출에서 0을 호출하게 된다면 1~g번째 게이트는 모두 사용중인것이니 더 이상 도킹이 불가능 하므로 현재까지 도킹 된 횟수를 출력해 주면 된다. 12345678910111213141516171819202122#includ.. 더보기