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

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

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