Servers Whose Failure Splits the Network
Solve this ProblemA network of servers is joined by cables (an undirected graph given as an adjacency list). A server is a key server if taking it out, together with its cables, leaves the remaining servers split into more separate parts than before. Find all key servers.
Removing each server and searching again works, but Tarjan's algorithm finds all of them in one depth-first search, again using discovery times and low-link values, with a slightly different test than for bridges and a special rule for the root.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 servers numbered 0 … n-1; graph[u] lists, in increasing order, every server joined to u by a cable (adjacency-list form of an undirected graph) - ◆
If v is in graph[u] then u is in graph[v]; there are no cables from a server to itself and no repeated cables - ◆
The network may consist of several separate parts - ◆
A server is a key server (articulation point) when taking it out of the network, together with its cables, increases the number of separate parts among the remaining servers. Return all key servers in increasing order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Take Out Each Server and Count the Separate Parts
BruteCount the separate parts of the network. Then, for each server in turn, pretend that server and its cables are gone and count the parts among the remaining servers with a breadth-first search. If the count is larger than before, the server was holding parts together, so it is a key server. Each server costs one full search.
O(n · (n + E))O(n)1class Solution {
2 private int countGroups(int[][] graph, int removed) {
3 int n = graph.length;
4 boolean[] seen = new boolean[n];
5 int groups = 0;
6 for (int start = 0; start < n; start++) {
7 if (start == removed || seen[start]) continue;
8 groups++;
9 seen[start] = true;
10 Deque<Integer> queue = new ArrayDeque<>();
11 queue.add(start);
12 while (!queue.isEmpty()) {
13 int u = queue.poll();
14 for (int v : graph[u]) {
15 if (v != removed && !seen[v]) {
16 seen[v] = true;
17 queue.add(v);
18 }
19 }
20 }
21 }
22 return groups;
23 }
24
25 public int[] keyServers(int[][] graph) {
26 int base = countGroups(graph, -1);
27 List<Integer> result = new ArrayList<>();
28 for (int u = 0; u < graph.length; u++) {
29 if (countGroups(graph, u) > base) result.add(u);
30 }
31 int[] answer = new int[result.size()];
32 for (int i = 0; i < answer.length; i++) answer[i] = result.get(i);
33 return answer;
34 }
35}Optimal — Tarjan’s Articulation-Point DFS
OptimalUse the same discovery-time and low-link idea as for bridges: disc[u] is when the depth-first search reaches u and low[u] the earliest discovery time reachable from u's subtree using at most one back edge. A server u that is not the root is a key server if it has a child v with low[v] ≥ disc[u]: the subtree of v cannot bypass u (with ≥ rather than the > used for bridges, because the back edge to u itself does not help once u is removed). The root of the search is a key server exactly when it has at least two children in the search tree. One pass, O(n + E).
O(n + E)O(n)1class Solution {
2 private int timer;
3
4 private void visit(int[][] graph, int u, int parent, int[] disc, int[] low, boolean[] key) {
5 timer++;
6 disc[u] = timer;
7 low[u] = timer;
8 int children = 0;
9 for (int v : graph[u]) {
10 if (v == parent) continue;
11 if (disc[v] != 0) {
12 low[u] = Math.min(low[u], disc[v]);
13 } else {
14 children++;
15 visit(graph, v, u, disc, low, key);
16 low[u] = Math.min(low[u], low[v]);
17 if (parent != -1 && low[v] >= disc[u]) key[u] = true;
18 }
19 }
20 if (parent == -1 && children >= 2) key[u] = true;
21 }
22
23 public int[] keyServers(int[][] graph) {
24 int n = graph.length;
25 int[] disc = new int[n];
26 int[] low = new int[n];
27 boolean[] key = new boolean[n];
28 timer = 0;
29 for (int start = 0; start < n; start++) {
30 if (disc[start] == 0) visit(graph, start, -1, disc, low, key);
31 }
32 List<Integer> result = new ArrayList<>();
33 for (int i = 0; i < n; i++) {
34 if (key[i]) result.add(i);
35 }
36 int[] answer = new int[result.size()];
37 for (int i = 0; i < answer.length; i++) answer[i] = result.get(i);
38 return answer;
39 }
40}