이분그래프3 BOJ 17038 - The great revegetation (유니온 파인드, 이분그래프) https://www.acmicpc.net/problem/17038 그래프가 이분그래프인지 아는법 기록 + 온라인쿼리 풀이 숙지 최대 1e5개의 목초지 n개가 있다고 할 때, 소(쿼리) m개가의 정보가 들어온다. 목초지는 두 그룹으로 나뉜다. S a b : a,b목초지가 같은 그룹에 있어야 해. D a b : a,b목초지가 다른 그룹에 있어야 해. 모든 목초지를 나누는 경우의 수를 구하라 오프라인 쿼리. s먼저 입력해서 merge해두고 d를 입력받으면서 a,b의 대표값을 간선으로 이어준다. 그래프가 이분그래프라면 컴포넌트마다 그룹을 나누는 경우가 두가지이므로 2^컴포넌트의 수가 정답. 그래프가 이분그래프가 아니면 그룹을 나눌 수 없다. int n, m, uf[MAX], vst[MAX]; vector ad.. 2020. 2. 22. BOJ 15475 - A pie for a pie (이분그래프, 이분탐색) https://www.acmicpc.net/problem/15457 유사코 골드. bessie와 elsie가 서로 선물을 교환한다. 같은 선물에 대해 각자 생각하는 가치가 다를 수 있다. 최대 1e5개의 선물을 둘이 같은 개수만큼 가지고 있다. 서로 선물을 교환하려 한다. 예를들어, bessie가 볼때 3의 가치를 지닌 선물을 bessie가 받은 경우 3이상 3+d이하(bessie기준)선물을 elsie에게 보답으로 준다. elsie도 마찬가지다. 이런 방법으로 계속 선물을 교환할 때, 본인이 생각했을 때 가치가 0인 선물을 받으면 성공적으로 선물 교환이 이뤄진 것으로 본다. bessie부터 선물을 주기로 한다. bessie의 i번째 선물을 처음으로 elsie에게 줬을 때 가장 적은 횟수로 성공적인 선물교.. 2020. 2. 18. 이분그래프 (bipartite graph) 어떤 그래프의 모든 노드를 두가지 색 중 하나로 칠하되, 이웃 노드의 색이 모두 다르게 만들 수 있다면 그 그래프는 이분그래프이다. 홀수개의 간선으로 이뤄진 사이클이 없으면 이분그래프이다! void dfs(int u, int p) { vst[u] = vst[p]==1?2:1; for (int v : adj[u]) { if (v == p) continue; if (vst[v] && !fin[v] && vst[v]==vst[u]) isNotBipartite = true; else if (!vst[v]) dfs(v, u); } fin[u] = true; } 2020. 1. 22. 이전 1 다음