본문 바로가기

disjoint set6

BOJ 11813 - GALAKSIJA (disjoint set, tree, 오프라인쿼리) https://www.acmicpc.net/problem/11813 http://blog.naver.com/nywoo19/221436385751 위 블로그 참고했습니다. 가중치있는 트리가 주어진다. 간선을 주어진 순서대로 자를 것. 자르고 난 후 원하는 값을 그때 그때 출력하는 문제. 원하는 값: 전체 경로에서 경로에포함된 모든 간선의 가중치의 xor값이 0인 경우의 수 트리를 자른다 -> 거꾸로 간선을 이어붙이는 편이 훨씬 쉽다. 1. a ^ b == 0 a == b 2. xor(u,v) : xor(1,u) ^ xor(1,v)임을 이용해야 한다. map mp[MAX]에서 mp[u] = {x, cnt} : 대표값이 u인 set에 포함된 v 중 xor(1,v)값이 x인 것의 개수 cnt 간선 (u,v)를 .. 2020. 3. 18.
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.

티스토리툴바