All Articles

Leetcode Contest 154, 155 - Graph

Sort Items by Groups Respecting Dependencies

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it’s equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

  • The items that belong to the same group are next to each other in the sorted list.
  • There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).

Return any solution if there is more than one solution and return an empty list if there is no solution.

Keyword: Graph, Topological sort, DAG

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. A directed graph doesn’t have topological sorting, if and only if it contains a cycle.

In this problem, we need to do a cycle check and topological sorting between groups, and inside each group need another check and topological sorting.


  1. Get the in_degree map for groups and for items
  2. Sort groups. By sorting here, we get all nodes whose in degree is 0 (which means no dependency), add them in a stack and update in_degree map, and do the process again until there are no nodes. Then pop nodes from stack and get the topological sort result.
  3. Sort inside each group


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] = [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.

Keyword: Graph, DFS

Basically it’s a DFS over all the nodes, the difficult part is to check whether an edge is a ‘critical connection’ or not. To define this edge [a,b], it’s critical if and only if there is no other way from a to reach b except this edge (not in a cycle).


from __future__ import print_function

from collections import defaultdict

class Solution(object):
    def criticalConnections(self, n, connections):
        :type n: int
        :type connections: List[List[int]]
        :rtype: List[List[int]]
        map = defaultdict(list)
        for [n1, n2] in connections:

        visited = defaultdict(lambda: False)
        # node with lowest index that this node can reach
        lowestNode = defaultdict(lambda: float('-inf'))
        # time that dfs went through this node, or depth in DFS
        discoverTime = defaultdict(lambda: float('-inf'))

        parentMap = defaultdict(lambda: -1)
        results = []

        def dfs(node, time):
            if visited[node]: return
            visited[node] = True
            lowestNode[node] = time
            discoverTime[node] = time

            for t in map[node]:
                # dfs over all adjacent nodes
                if not visited[t]:
                    parentMap[t] = node
                    dfs(t, time + 1)
                    lowestNode[node] = min(lowestNode[t], lowestNode[node])

                    if lowestNode[t] > discoverTime[node]:
                        results.append([node, t])
                    if t != parentMap[node]:
                        lowestNode[node] = min(lowestNode[node], discoverTime[t])

        dfs(0, 0)
        return results

n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
print(Solution().criticalConnections(n, connections))