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.

Steps:

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

Reference:

• Topological sorting

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).

• Another post to explain ‘Bridges in a graph’
• Tarjan’s Algorithm to find Strongly Connected Components, which is the hint of this question but it’s for directed graph

Solution:

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:
            map[n1].append(n2)
            map[n2].append(n1)

        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])
                else:
                    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))