오프라인쿼리2 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 15586 - Moo tube ( 오프라인 쿼리, 유니온 파인드 ) https://www.acmicpc.net/problem/15586 왜 정답률이 65퍼인지 궁금한 문제 자연수 가중치가 있는 트리가 주어진다. 정점 u~v경로 상의 가중 치 중 가장 작은 값을 usado(u,v)라고 한다. 최대 1e5개의 쿼리 (ki, vi)가 주어진다. vi와 연결된 정점 중 유사도가 ki이상인 정점의 수를 구하라. V^2에 풀수있지만 TLE. 아예 다른방법으로 접근해야 한다. 임의의 정점에 대해 유사도 ki이상인 정점을 구하려면 가중치가 ki이상인 간선들만 필요하다. ->가중치가 ki 이상인 간선들로만 이뤄진 스패닝 트리를 두고 생각하면 편해진다. 쿼리를 ki에 대해 내림차순으로 정렬하고 간선도 가중치 기준으로 내림차순 정렬한다. 쿼리를 순차로 보면서, ki이상의 가중치를 가진 간선.. 2020. 2. 19. 이전 1 다음