상호배타적 집합 (1) 썸네일형 리스트형 유니온 파인드[Union Find] 유니온 파인드(Union Find) 그래프 알고리즘의 일종으로서 서로소 집합, 상호 배타적 집합(Disjoint-set)이라고도 한다. 알고리즘 문제 풀이에서는 주로 집합을 나타내며 합집합만 사용할 때 쓰인다. 여러 노드가 존재할 때, 선택한 두 노드를 같은 그래프로 합치거나 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. Parent[x] : x의 부모 노드 Find : x가 속한 집합의 root 노드를 반환하는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 Parent 초기화 vector parent(n); for (int i = 0; i 부모 자식 관계는 중요하지 않음(단지 유니온 연산을 하다가 나온것) -> 하나로 묶여 있다는것이 중요함. -> 가장 중요한것은 루트. 최종 루.. 이전 1 다음
