우주수첩의 우주먼지

https://cses.fi/problemset/task/1676/ CSES - Road Construction cses.fi #include #include using namespace std; const int N = 200001; class UFDS { private: vector p, rank, setSizes; int numSets; public: UFDS(int N) { numSets = N; rank.assign(N, 0); p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; setSizes.assign(N, 1); } int findSet(int i) { return (p[i] == i) ? i : p[i] = findSet(p[i]); } bo..

Union-FInd 그래프 알고리즘 중 하나로 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하하는지 판별하는 알고리즘. disjoint set들을 관리하기 위한 data structure makeset(x) : 단일 element x로 이루어진 set을 하나 생성한다. find(x) : x가 포함된 set을 return한다. union(x,y) : x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다. union-find는 각 set을 rooted tree로 관리하고, 각 tree의 root를 대표 element로 지정한다. 각 대표 element는 rank를 가지고 있다. rank는 해당 tree의 height로 정의하며, union 시 rank가 작아지는 쪽으로 un..

최소 스패닝 트리(MST)를 만들기 위한 방법 중 하나. (+ 프림알고리즘) 1. 모든 간선들의 가중치를 오름차순으로 정렬한다. 2. 가중치가 가장 작은 간선을 선택한다. 3. 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면 2개의 노드를 서로 연결한다. 4. 반복. => 최소가중치를 가진 간선들을 사이클이 발생하지 않게 계속 연결하여 MST를 찾는다. 시간 복잡도 : O(mlog n) 구현 가장 작은 가중치를 갖는 간선이 연결하고자 하는 두 노드가 연결되어있는지 확인해주는 과정에서 많이 사용하는 방식이 Union-Find이다. 이전에 Union_Find를 다룬 적이 있는데 이를 이렇게 적용할 줄이야 하하핳. parent[] 코드 구현시에 대중적으로 많이 사용하는 방법은 pare..