DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

1 1

Critical Connections in a Network

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

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

Return all critical connections in the network in any order.

Example 1:

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

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

Constraints:

  • 2 <= n <= 105
  • n - 1 <= connections.length <= 105
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • There are no repeated connections.

SOLUTION:

from collections import defaultdict

class Solution:
    def DFS(self, graph, node, v, parent, disc, low):
        v.add(node)
        disc[node] = self.t
        low[node] = self.t
        self.t += 1
        for j in graph[node]:
            if j not in v:
                parent[j] = node
                self.DFS(graph, j, v, parent, disc, low)
                low[node] = min(low[node], low[j])
            elif j != parent[node]:
                low[node] = min(low[node], disc[j])

    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        for a, b in connections:
            graph[a].append(b)
            graph[b].append(a)
        self.t = 0
        parent = defaultdict(lambda: -1)
        disc = defaultdict(lambda: float('inf'))
        low = defaultdict(lambda: float('inf'))
        v = set()
        for i in range(n):
            if i not in v:
                self.DFS(graph, i, v, parent, disc, low)
        return [[u, v] for u, v in connections if low[u] > disc[v] or low[v] > disc[u]]
Enter fullscreen mode Exit fullscreen mode

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay