Created
December 24, 2020 22:02
-
-
Save adamgarcia4/1db35fefac977788a441974c1ad99bda to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
# This function updates the lowLink of nodeNum. | |
def dfs(self, at, parent, bridges): | |
# Initialize current node | |
self.visited[at] = True | |
self.lowLink[at] = self.rankNum | |
self.ids[at] = self.rankNum | |
self.rankNum += 1 | |
for to in self.adjList[at]: | |
# don't consider going back to the node that I came from | |
if to == parent: | |
continue | |
# If I haven't visited this node | |
if not self.visited[to]: | |
self.dfs(to, at, bridges) | |
# backtrack stage | |
self.lowLink[at] = min(self.lowLink[at], self.lowLink[to]) | |
# If the lowest link (node) reachable from 'to' is not what has already been seen, | |
# Then there is no cycle, and this edge constitutes a 'bridge'. | |
if self.ids[at] < self.lowLink[to]: | |
bridges.append([at, to]) | |
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]: | |
''' | |
Key Observation: | |
A series of edges that make up a cycle are NOT bridges. | |
Any edge that does not make up a cycle, | |
Basically, do a cycle detection, but instead of returning T/F, | |
we want to know the exact cycle that each end of the edge is a part of. | |
If these nodes are part of the same cycle, then this is not a critical edge. | |
If they aren't, then this is a critical edge. | |
We do this with a 'parentId' for each node. This is defined as the MINIMUM id reachable from the node. | |
This can be done in a DFS manner. | |
ParentId can be initialized to itself. | |
As I do DFS, if the outNode is a lower value than the parentId, then adjust. | |
This needs to be done recursively. | |
Maintain visited to not go into infinite cycle. | |
''' | |
# Build up Adj List | |
self.adjList = [[] for _ in range(n)] | |
for u, v in connections: | |
self.adjList[u].append(v) | |
self.adjList[v].append(u) | |
# Setting up storage | |
self.visited = [False] * n | |
self.lowLink = [x for x in range(n)] # starts pointing to myself | |
self.ids = [-1] * n | |
self.rankNum = 0 | |
res = [] | |
for nodeNum in range(n): | |
if self.visited[nodeNum]: | |
continue | |
self.dfs(nodeNum, -1, res) | |
return res |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment