1319. Number of Operations to Make Network Connected - medium
문제
There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network.
Given an initial computer network connections.
You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected.
If it’s not possible, return -1.
제한사항
- 1 <= n <= 10^5
- 1 <= connections.length <= min(n*(n-1)/2, 10^5)
- connections[i].length == 2
- 0 <= connections[i][0], connections[i][1] < n
- connections[i][0] != connections[i][1]
- There are no repeated connections.
- No two computers are connected by more than one cable.
입출력 예
1
2
3
4
Example 1:
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.
1
2
3
Example 2:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2
1
2
3
4
Example 3:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.
1
2
3
Example 4:
Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output: 0
풀이
- DFS, BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if(n - 1 > connections.size())
return -1;
int countUnion = 0;
vector<vector<int>> connectionsMap(n, vector<int>());
vector<bool> visited(n, true);
// connections기반으로 connectionsMap을 구성
for(const auto connection : connections){
connectionsMap[connection[0]].push_back(connection[1]);
connectionsMap[connection[1]].push_back(connection[0]);
}
// index하나씩 검사하여 구성된 집함의 갯수를 조사
for(auto index = 0 ; index < n ; ++index){
// 현재 index에 대하여 이미 조회했다면 패스
if(!visited[index])
continue;
stack<int> s;
// DFS
s.push(index);
while(!s.empty()){
auto nodeIndex = s.top();
s.pop();
// 현재 index를 조회했으니 체크
visited[nodeIndex] = false;
// 현재 index와 연결된 모든 노드들을 탐색
for(auto i : connectionsMap[nodeIndex]){
if(visited[i]){
s.push(i);
}
}
}
++countUnion;
}
return countUnion - 1;
}
};