본문 바로가기

유니온 파인드2

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.

티스토리툴바