Python | Two approaches: Backtracking and Tarjan's w/union-find
First attempt was using backtracking. Turned out to be too slow and TLE\'d. Decided to read on Tarjan\'s algorithm, as the hint suggested, and implemented the s
First attempt was using backtracking. Turned out to be too slow and TLE\'d. Decided to read on Tarjan\'s algorithm, as the hint suggested, and implemented the second solution.\n\nIn both solutions we used **union-find** to label the strongly connected components. Then traversed the graph once more to identify critical connections by checking if there were edges connecting two different strongly connected components.\n\n# **Backtracking (TLE)**\nThis solution passed individual (heavy) test cases, but not all at once. **Passed 14/17 test cases**.\n\n```\nclass Solution:\n    def union(self, i: int, j: int):\n        self.parent[i] = j        \n        \n    def find(self, i: int):\n        if self.parent[i] == i:\n            return i\n        return self.find(self.parent[i])\n    \n    def backtrack(self, i: int, k: int):\n        if self.inCurrentCyclees[i]:\n            for j in reversed(self.currentCyclees):\n                if j != i:\n                    self.union(j, i)\n                else:\n                    break\n        else:\n            self.currentCyclees.append(i)\n            self.inCurrentCyclees[i] = True\n            for j in self.graph[i]:\n                if j != k and self.find(j) != self.find(i):\n                    self.backtrack(j, i)\n            self.currentCyclees.pop()\n            self.inCurrentCyclees[i] = False\n    \n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n\t\t# build graph\n        self.graph = defaultdict(set)\n        for a, b in connections:\n            self.graph[a].add(b)\n            self.graph[b].add(a)\n\t\t\n\t\t# find strongly connected components\n        self.currentCyclees, self.inCurrentCyclees = [], [False] * n \n        self.parent = [i for i in range(n + 1)]\n        self.backtrack(0, n)\n        \n\t\t# identify critical connections\n        toReturn = []\n        for i in range(n):\n            for j in self.graph[i]:\n                if i < j and self.find(j) != self.find(i):\n                    toReturn.append([i, j])\n                    \n        return toReturn\n```\n# **Tarjan\'s from Wikipedia (with small modifications)**\nImplemented Tarjan\'s strongly connected components algorithm as described in <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">Wikipedia</a> to identify strongly connected components. Just modified it a bit to take in consideration that this was an undirected graph. \n```\nclass Solution:\n    def union(self, i: int, j: int):\n        self.parent[i] = self.find(j)\n        \n    def find(self, i: int):\n        if self.parent[i] == i:\n            return i\n        return self.find(self.parent[i])\n    \n    def strongConnect(self, i: int, k: int):\n        self.index[i] = self.currIndex\n        self.lowLink[i] = self.currIndex\n        self.currIndex += 1\n        self.stack.append(i)\n        self.onStack[i] = True\n            \n        for j in self.graph[i]:\n            if self.find(j) != self.find(k):\n                if self.index[j] is None:\n                    self.strongConnect(j, i)\n                    self.lowLink[i] = min(self.lowLink[i], self.lowLink[j])\n                elif self.onStack[j]:\n                    self.lowLink[i] = min(self.lowLink[i], self.index[j])\n                \n        if self.lowLink[i] == self.index[i]:\n            while self.stack:\n                j = self.stack.pop()\n                self.onStack[j] = False\n                if i == j:\n                    break\n                else:\n                    self.union(j, i)\n    \n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        # build graph\n        self.graph = defaultdict(set)\n        for a, b in connections:\n            self.graph[a].add(b)\n            self.graph[b].add(a)\n        \n        # setup for strongConnect\n        self.index, self.lowLink = [None] * n, [0] * n\n        self.stack, self.onStack = [], [False] * n\n        self.currIndex = 0\n        self.parent = [i for i in range(n + 1)]\n        \n        # find strongly connected components\n        for i in range(n):\n            if self.index[i] is None:\n                self.strongConnect(i, n)\n        \n        # identify critical connections\n        toReturn = []\n        for i in range(n):\n            for j in self.graph[i]:\n                if i < j and self.find(j) != self.find(i):\n                    toReturn.append([i, j])\n                    \n        return toReturn\n```
['Depth-First Search', 'Union Find', 'Python']