Leetcode - Critical Connections in a Network (Python)

April 2021 Leetcode Challenge
Leetcode - Critical Connections in a Network #1192
Difficulty: Hard

[kingKabali]

I don't know tarjan's algorithm .... proceeds to explain it.

[janmichaelaustria]

This one sucked....but after looking into it more I think the brute force is little more understandable (especially because I don't know Tarjans >.<).

We can just try dropping one bridge at a time, do a dfs, and see if the state with the current dropped bridge is difference than the initial. For states, I just used frozensets. It gets TLE, but I think it's a really good starting point for this problem. Thanks for the video once again Tim!

class Solution(object):
def criticalConnections(self, n, connections):
"""
:type n: int
:type connections: List[List[int]]
:rtype: List[List[int]]
"""
#dfs on the graph after removing and edge
adj_list = defaultdict(list)
for a, b in connections:
adj_list[a].append(b)
adj_list[b].append(a) #need to add complements because it is undirected

#define dfs, traverse the graph and return the visited set
def dfs(node):
seen.add(node)
for neigh in adj_list[node]:
if neigh not in seen:
dfs(neigh)
#i dont know if dfsing from each node would give me disconnected graph
#invoke on each n, freeze the set, add to it and call it init start
initial_state = set()
for i in range(n):
seen = set()
dfs(i)
temp = []
for v in seen:
temp.append(v)
temp = frozenset(temp)
initial_state.add(temp)

bridges = set()

#now simulate dropping an edge
for i in range(len(connections)):
dropped = copy.deepcopy(connections)
del dropped[i]
#build_adj for dropped edge
adj_list = defaultdict(list)
for a, b in dropped:
adj_list[a].append(b)
adj_list[b].append(a)
#but now i have to dfs for all the nodes in this curr adjlist
curr_state = set()
for j in range(n):
seen = set()
dfs(j)
temp = []
for v in seen:
temp.append(v)
temp = frozenset(temp)
curr_state.add(temp)
if curr_state != initial_state:
v1, v2 = connections[i]
bridges.add((v1, v2))
return bridges

[almasabdrazak]

maybe I am a dumb but why do you make a undirected graph if you always skip the parent, I think directed graph can be used, not sure though hehe