백준 18116. 로봇 조립
https://www.acmicpc.net/problem/18116
18116번: 로봇 조립
성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의
www.acmicpc.net
Union Find 알고리즘으로 두 부품이 같은 집합에 속하는지 판단하면 된다.
https://tose33.tistory.com/614
Union-Find Algorithm
https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221230967614&referrerCode=0&searchKeyword=union 17. Union-Find(합집합 찾기) Union-Find(유니온-파인드)는 대표적인 그래프 알고리즘입니다. 바로 '합집합 찾기'라는
tose33.tistory.com
입력으로 Q 가 들어왔을때 두 부품이 속한 집합의 노드의 수를 구해야 한다.
이건 두 노드 n1,n2를 Union 처리할때 최상위 부모 노드 (루트 노드) 에 총 노드수를 기록하면 된다.
예를들어 n1 - n2 - n3 이 현재 집합1이고 n4 - n5 가 집합2 라고 해보자.
Union(n3, n4) 를 하면 두 집합이 하나의 집합으로 합쳐지고 루트 노드는 n1 이된다.
(작은 노드를 부모로 한다고 할때)
n1 - n2 - n3 - n4 - n5
n3 = GetParent(n3), n4 = GetParent(n4); // union 처리 이전에 n3 과 n4 의 부모를 구한다. 각각 n1, n4 이다.
count[min(n1,n4)] += count[max(n1,n4)] //