본문 바로가기

Union Find4

BOJ 12012 - Closing the farm (유니온파인드) https://www.acmicpc.net/problem/12012 거꾸로 생각해서 쉬워지는 문제 최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다. 각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다. 문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다) 쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다. 정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 .. 2020. 2. 7.
codeforces #603 div2 D - Secrete Passwords ( 이분매칭, disjoint set ) http://codeforces.com/contest/1263/problem/D editorial은 biparite graph 어쩌고로 풀던데, 나는 유파로 풀었다. 문자열이 최대 2e5개 들어온다. . i번째 문자열과 j번째 문자열이 단 한 개라도 같은 알파벳을 사용했다면 두 문자열은 equivalent다 . k번째와 i번째 문자열이 equivalent하고 k번째와 j번째 문자열이 equivalent하다면 i번째와 j번째는 equivalent다. 위 상황에서 컴포넌트의 수를 구하는 문제이다. 간선만 잘 깔아주면 된다. 하지만 n이 커서 단순히 모든 요소를 비교하는 식으로 간선을 이을 수 없다. bool s[MAX][26] = { 0 }; string 형으로 문자열을 입력받은 후, 위에 저장해 뒀다. (.. 2019. 12. 2.
codeforces #600 div2 D - Harmonious Graph ( disjoint set ) https://codeforces.com/contest/1253/problem/D 처음으로 버츄얼이 아닌 실제 시험에서 4솔을 했다. undirected 그래프가 harmonious -> if and only if, For every triple of integers (l,m,r) such that 1≤l> m; fill(uf, uf + MAX, -1); P e[MAX]; vector can; for (int i = 0, u, v; i > u >> v; if (u > v) swap(u, v); merge(u, v); e[i] = { u,v }; } sort(e, e + m); int st = e[0].first, en = e[0].second; for (int i = 1; .. 2019. 11. 20.
BOJ 16562 - 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. www.acmicpc.net 유니온파인드 문제다. 각 집합의 최소를 모두 더한 합을 출력하면 된다. #include #include using namespace std; int n, m, k; int uf[10001]; int cost.. 2019. 8. 6.

티스토리툴바