### 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:

- Get the
`in_degree`

map 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
`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. - Sort inside each group

Reference:

### 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))
```