Halo

A magic place for coding

0%

LeetCode 解题报告(355) -- 1192. Critical Connections in a Network

Problem

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections [i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Example1

1
2
3
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

  • 1 <= n <= 10^5
  • n-1 <= connections.length <= 10^5
  • connections [i][0] != connections [i][1]
  • There are no repeated connections.

Analysis

   题目给出了一个图,要求我们找到所有的 critical 边,对 critical 的定义是一旦删除这条边,某些节点就会失去和其他节点的连接。先理解一下题意,这里涉及到了连通分量的问题。critical 边实际的意义就是,一旦移除,就会多一个连通分量。

   一下子好像无从下手,我们先来看什么是连通分量。以 Example1 为例,如果用 1 作为起点,它有两条路(注意这里的每一步,不能往前一个点走,但是可以走访问过的点):

  1. 往 3 走,然后就结束;
  2. 往 0 走,然后往 2 走,最后回到 1,结束(或者是往 2 走,然后往 0 走,最后回到 1,结束)。

   对于 1 这个点来说,这两条路径是不一样的,第一条路实际上就是题目要找的 critical 边,而第二条路实际上是回环,并不存在 critical 边。所以我们的重点在于,如何去判断出第一条路径是有 critical 边,而第二条路径没有。

   这里就要介绍一个图论中一个很重要的算法 ——**Tarjan 算法 **。这里我们不纠结于算法具体是什么或者完整实现是怎么样的,我们借助它的核心思路,然后直接来看应用到这道题上怎么做。其核心思想是 ** 基于深度优先解决图的连通性问题 **,这个点给了我很大的提示。我们要利用深度的信息去判断图的连通性,这个要怎么做呢?还是回到 Example1 中,还是用 1 作为起点,如果此时把 1 的深度定义为 0,用 DFS,那么它往后遍历每一个节点,深度就自增 1。按照上面的两条路径:

  1. 节点 3 的深度是 1,结束;
  2. 节点 0 的深度是 1,节点 2 的深度是 2,然后去到节点 1 的深度是 0(这里不用更新为 3,因为节点 1 的深度已经定义过了)。

   根据这个深度我们能判断出来,如果 dfs 最后节点的深度大于当前的深度,则说明当前节点和最后的这个节点它们之间不能形成环,因此它们直接的 connection 就是 critical 的。这里需要注意 dfs 返回的结果是该节点往后的子孙节点中的 ** 最小深度 **。然后我们记录每一个节点的最小深度,如果已经访问过了,就不需要再做一遍 dfs 了。


Solution

   无


Code

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
48
49
class Solution {
public:
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
vector<vector<int>> result;
vector<int> depthArr(n, -1);
vector<vector<int>> map(n, vector<int>());

int size = connections.size ();
//construct connection map
for (int i = 0; i < size; i++) {
map[connections [i][0]].push_back (connections [i][1]);
map[connections [i][1]].push_back (connections [i][0]);
}

dfs (0, 0, 0, map, depthArr, result);
return result;
}

private:
int dfs(int current, int previous, int depth, vector<vector<int>> &map, vector<int> &depthArr, vector<vector<int>>& result) {
depthArr [current] = depth;
int minDepth = INT_MAX;


for (int i: map[current]) {
if (i == previous) {
//not go back
continue;
}
int endDepth;
if (depthArr [i] == -1) {
//not visited
endDepth = dfs (i, current, depth + 1, map, depthArr, result);
if (endDepth > depth) {
//the end point is deeper than the current point
//means that the current point is not in the circle
vector<int> temp;
temp.push_back (current);
temp.push_back (i);
result.push_back (temp);
}
} else {
endDepth = depthArr [i];
}
minDepth = min (minDepth, endDepth);
}
return minDepth;
}
};

Summary

   这道题目是难度很大的图论题目,据说是亚麻的面试题。在做这道题目前确实在这方面没什么经验,这道题目提供了一个解决类似问题的思路,利用 dfs 来计算子孙节点的深度,通过深度来判断连通性。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels