2-Sat2 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. 2-SAT(Boolean Satisfiability) F = (a||b) && (c||d) && (e||f).... (||대신 xor등으로 변형가능함) 다음과 같이 F가 주어질 때, 1. F가 참이나 거짓이 되도록 할 수 있는지 여부 2. F가 참/거짓일 떄 a,b,c,d,e,f,..의 값은 무엇인지 를 묻는 문제들이 대표적이다. 배경지식: 0. p->q == notp or q . p가 false라면 p->q는 항상 참이다. 1. p || q == notp -> q && notq->p (두 항이 대우관계로 같은 말이다. 방향이 반대인 그래프를 하나 더 그려주기 위함인 것으로 이해함.) 2. p xor q == (notp -> q && notq->p) && (p->notq && q->notp) (묶인 것 끼리 대우관계이다. 위와 같은 이유라고 이해함.) 3... 2019. 8. 19. 이전 1 다음