우주수첩의 우주먼지

https://cses.fi/problemset/task/1675/ CSES - Road Reparation cses.fi 망할 알고리즘 응용 덕분에 크루스칼 제대로 머리에 기억 남을 듯 하다. 물론 얼마나 갈지는 모르겠지만. #include #include #include using namespace std; vector Edge; 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 ..

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