C# Trajan's Algorithm + unit test
Tarjan Algorithm is an algorithm to find strongly connected components.\nthese are basically vertices(nodes) in a directed graph, which you can get from any ver
Tarjan Algorithm is an algorithm to find strongly connected components.\nthese are basically vertices(nodes) in **a directed graph**, which you can get from any vertex to another vertex, our graph is not directed so when we build the graph we put the node in and not out \nand then node out and node in, that way we have both edges(directions)\n\nafter that we need to remember which vertices we already visited. so we init an array to -1.\nwe iterate the number of nodes. for each node we didn\'t visit already we run a DFS.\nuntil now this is just understanding the graph and running a DFS.\nTarjan algorithm is used for topological sorting and it is based on DFS, everytime you reach a node which doesn\'t have any neighbours you add that node into the front of the list for topological sorting.\n\nin here when we run the DFS we have the visited array and low array.\n\nfirst time the DFS visits a new vertex we enter "time"( a private variable of the class) into visited and low array, and we increment time by 1.\n\nwe then iterate all of u (the current vertex neighbors) with the DFS, the DFS knows what is the previous vertex we visited so if one of the neighbours of u is prev we skip it.\n\nif we didn\'t visit one of u\'s neighbours we call the DFS function again this time u is previous vertex.\nthen we compare low[v] **(u\'s neighbour after DFS)** and low[u] and update low[u] to be the minimal of the 2.\n\nif low of the neighbour is greater than visited of the current vertex u\n\nthat means we only one way to get from u to its\' neighbour (GREAT Success)!\nthat means if we takes this out there is no way to get from u to the neighbour.\n\nso we add that edge from u to neighbour(called v) to the result.\n\nelse we already visited u\'s neighbour then we update low of u to be the min of low[u] and visited of the neighbour\n\n```\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing Microsoft.VisualStudio.TestTools.UnitTesting;\n\nnamespace GraphsQuestions\n{\n    /// <summary>\n    /// https://leetcode.com/problems/critical-connections-in-a-network/\n    /// </summary>\n    [TestClass]\n    public class CriticalConnectionsInANetwork\n    {\n        [TestMethod]\n        public void TestMethod1()\n        {\n            //[[0,1],[1,2],[2,0],[1,3]]\n            List<IList<int>> input = new List<IList<int>>();\n            input.Add(new List<int> { 0, 1 });\n            input.Add(new List<int> { 1, 2 });\n            input.Add(new List<int> { 2, 0 });\n            input.Add(new List<int> { 1, 3 });\n            CriticalConnectionsClass ccClass = new CriticalConnectionsClass();\n            var res = ccClass.CriticalConnections(4, input);\n            List<IList<int>> expcted = new List<IList<int>>();\n            expcted.Add(new List<int> { 1,3 });\n            for (int i = 0; i < res.Count; i++)\n            {\n                CollectionAssert.AreEqual(expcted[i].ToList(), res[i].ToList());\n            }\n        }\n    }\n\n    public class CriticalConnectionsClass\n    {\n        //time when discovered the vertex\n        private int time = 0;\n        public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections)\n        {\n            int[] low = new int[n];\n            List<IList<int>> result = new List<IList<int>>();\n            //we init the visited array to -1 for all vertices\n            int[] visited = Enumerable.Repeat(-1, n).ToArray();\n\n            Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();\n            //the graph is connected two ways\n            foreach (var list in connections)\n            {\n                if (!dict.ContainsKey(list[0]))\n                {\n                    dict.Add(list[0], new List<int>());\n                }\n                dict[list[0]].Add(list[1]);\n\n\n                if (!dict.ContainsKey(list[1]))\n                {\n                    dict.Add(list[1], new List<int>());\n                }\n                dict[list[1]].Add(list[0]);\n\n            }\n\n            for (int i = 0; i < n; i++)\n            {\n                if (visited[i] == -1)\n                {\n                    DFS(i, low, visited, dict, result, i);\n                }\n            }\n            return result;\n        }\n\n        private void DFS(int u, int[] low, int[] visited, Dictionary<int, List<int>> dict, List<IList<int>> result, int pre)\n        {\n            visited[u] = low[u] = ++time; // discovered u;\n            for (int j = 0; j < dict[u].Count; j++) //iterate all of the nodes connected to u\n            {\n                int v = dict[u][j];\n                if (v == pre)\n                {\n                    //if parent vertex ignore\n                    continue;\n                }\n\n                if (visited[v] == -1) // if not visited\n                {\n                    DFS(v, low, visited, dict, result, u);\n                    low[u] = Math.Min(low[u], low[v]);\n                    if (low[v] > visited[u])\n                    {\n                        //u-v is critical there is no path for v to reach back to u or previous vertices of u\n                        result.Add(new List<int> { u, v });\n                    }\n                }\n                else // if v is already visited put the minimum into low for vertex u\n                {\n                    low[u] = Math.Min(low[u], visited[v]);\n                }\n            }\n        }\n    }\n\n}\n```\n
[]