www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구의 관계가 주어진다. 예제를 보면 Fred Barney Betty Wilma Barney Betty 가 주어지는데 Fred - Barney 가 연결되었으니 총 2명 Betty - Wilma 가 연결되었으니 총 2명 Barney - Betty 인데 Betty - Wilma, Barney - Fred 가 서로 친구이니 총 4명 즉, 집합이 주어지는데 같은 부모 노드 같은 구성원이 존재한다면 Union..

Disjoint-Set (서로수 집합) 이라고도 불리는 유니온 파인드는 여러 집합이 주어지면 각 집합의 루트 노드가 무엇인지, 또는 Union(합집합) 연산을 손쉽게 하기 위한 일종의 자료구조이다. 큰 틀로는 집합의 부모 노드를 찾는 find 함수, 각 집합을 병합하는 union 함수를 만들어주면 된다. int find(int x) { if (parent[x] < 0) return x; parent[x] = find(parent[x]); return parent[x]; } find 함수부터 살펴보면 parent배열의 초기값은 -1로 설정해둔다(이후에 집합의 크기를 알기 쉽게 하기 위해) 만약 parent [x]가 0보다 작다는 소리는 그 노드가 루트 노드임을 알 수 있다. 그대로 x를 반환하면 된다. 만..