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.
- Get the
in_degreemap for groups and for items
- Sort groups. By sorting here, we get all nodes whose in degree is 0 (which means no dependency), add them in a
stackand update in_degree map, and do the process again until there are no nodes. Then pop nodes from
stackand get the topological sort result.
- Sort inside each group
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
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))