유파3 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. BOJ 12012 - Closing the farm (유니온파인드) https://www.acmicpc.net/problem/12012 거꾸로 생각해서 쉬워지는 문제 최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다. 각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다. 문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다) 쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다. 정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 .. 2020. 2. 7. Union Find (=disjoint set) 필요한 것: uf배열. find 함수 : 1. uf 배열이 -1로 초기화된 경우 2. uf 배열이자기자신으로 초기화된 경우 merge 함수: 1. merge함수가 일반적으로 union의 기능만을 수행하는 경우 2. MST등에서 union에 성공했을 떄 true, 실패했을 때 false 반환하는 경우 3. merge 후 대표정점(집합)에 포함된 요소의 크기를 초기화해주는 경우 등등등.. 상황에 맞게 구현할 수 있다 int uf[MAX]; //uf배열이 -1로 초기화된 경우 int find(int a) { if (uf[a] == -1) return a; return uf[a] = find(uf[a]); } //union기능만 수행 void merge(int a, int b) { a = find(a); b =.. 2019. 8. 18. 이전 1 다음