# LeetCode: critical connections in a network C# (Tarjan's algorithm)

https://leetcode.com/problems/critical-connections-in-a-network/

Please review for memory and runtime performance.

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. Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted.

Constraints:

1 <= n <= 10^5 n-1 <= connections.length <= 10^5 connections[i] != connectionsi There are no repeated connections.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace GraphsQuestions
{
/// <summary>
/// https://leetcode.com/problems/critical-connections-in-a-network/
/// </summary>
[TestClass]
public class CriticalConnectionsInANetwork
{
[TestMethod]
public void TestMethod1()
{
//[[0,1],[1,2],[2,0],[1,3]]
List<IList<int>> input = new List<IList<int>>();
input.Add(new List<int> { 0, 1 });
input.Add(new List<int> { 1, 2 });
input.Add(new List<int> { 2, 0 });
input.Add(new List<int> { 1, 3 });
CriticalConnectionsClass ccClass = new CriticalConnectionsClass();
var res = ccClass.CriticalConnections(4, input);
List<IList<int>> expcted = new List<IList<int>>();
for (int i = 0; i < res.Count; i++)
{
CollectionAssert.AreEqual(expcted[i].ToList(), res[i].ToList());
}
}
}

public class CriticalConnectionsClass
{
//_time when discovered the vertex
private int _time = 0;
public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections)
{
int[] low = new int[n];
List<IList<int>> result = new List<IList<int>>();
//we init the visited array to -1 for all vertices
int[] visited = Enumerable.Repeat(-1, n).ToArray();

Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();
//the graph is connected two ways
foreach (var list in connections)
{
if (!dict.ContainsKey(list))
{
}

if (!dict.ContainsKey(list))
{
}

}

for (int i = 0; i < n; i++)
{
if (visited[i] == -1)
{
DFS(i, low, visited, dict, result, i);
}
}
return result;
}

private void DFS(int u, int[] low, int[] visited, Dictionary<int, List<int>> dict, List<IList<int>> result, int pre)
{
visited[u] = low[u] = ++_time; // discovered u;
for (int j = 0; j < dict[u].Count; j++) //iterate all of the nodes connected to u
{
int v = dict[u][j];
if (v == pre)
{
//if parent vertex ignore
continue;
}

if (visited[v] == -1) // if not visited
{
DFS(v, low, visited, dict, result, u);
low[u] = Math.Min(low[u], low[v]);
if (low[v] > visited[u])
{
//u-v is critical there is no path for v to reach back to u or previous vertices of u
result.Add(new List<int> { u, v });
}
}
else // if v is already visited put the minimum into low for vertex u
{
low[u] = Math.Min(low[u], visited[v]);
}
}
}
}

}