[leetcode][1319] Number of Operations to Make Network Connected

문제 : https://leetcode.com/problems/number-of-operations-to-make-network-connected/

---

컴퓨터의 총 개수와 네트워크 연결 여부를 저장한 배열이 주어졌을 때, 모든 컴퓨터들이 네트워크에 연결하기 위해 이동이 필요한 네트워크 연결 수 를 반환하는 문제. (불가능하다면 -1)

 

최소 신장 트리의 간선 수는 N-1개이다. 비슷하게 이 문제에서 불가능한 네트워크 개수는 컴퓨터의 총 개수 - 1 보다 작은 경우들이다. 

이 경우를 만족한다면 모든 컴퓨터들이 네트워크에 연결이 가능하다.

Union-Find를 이용해서 네트워크 번호를 하나의 배열에 저장한다.

즉, a, b 컴퓨터가 같은 네트워크에 있다면 배열[a], 배열[b]는 같은 값을 가진다.

네트워크 배열을 다 구했다면 이 배열들이 모두 하나로 연결되어야 하므로 이들(네트워크 무리)을 연결하기 위한 간선의 개수는 앞에서 구한 것과 비슷하게 네트워크 무리 개수 - 1이다. 이게 정답이 된다.

 

시간복잡도는 O(NlogN). 네트워크 무리 개수를 구하기 위해 set을 이용했는데 여기서 가장 오래 시간이 걸린다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1319.%20Number%20of%20Operations%20to%20Make%20Network%20Connected.cpp