Union Find (Disjoint Set) | Explanation + Visual | [Python]
TL;DR (visuals + explanation below) this problem can be solved by finding the minimum cost spanning tree  with kruskal\'s algorithm via a disjoint set data stru
***TL;DR*** (visuals + explanation below) this problem can be solved by finding the ***minimum cost spanning tree***  with ***kruskal\'s algorithm*** via a ***disjoint set*** data structure. Our problem deals with  special case of the *minimum cost spanning tree problem*  where ***edge weights*** have a value of ```1``` and ties are broken by a predefined ordering. \n\n```python\nclass DisjointSet:\n    def __init__(self, n):\n        self.disjoint_set = [-1 for _ in range(n + 1)]\n        self.disjoint_set[0] = float(\'-inf\')\n        self.cycle = None\n    \n    def find(self, vertex):\n        while self.disjoint_set[vertex] > 0:\n            vertex = self.disjoint_set[vertex]\n        return vertex, self.disjoint_set[vertex]\n    \n    def union(self, edge):\n        u, v = edge\n        s1, r1 = self.find(u)\n        s2, r2 = self.find(v)\n        if s1 != s2:\n            if r1 <= r2:\n                self.disjoint_set[s1] -= 1\n                self.disjoint_set[s2] = s1\n            else:\n                self.disjoint_set[s2] -= 1\n                self.disjoint_set[s1] = s2 \n        else:\n            self.cycle = edge \n            \nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        vertices = set()\n        for u, v in edges:\n            vertices.add(u)\n            vertices.add(v)\n        \n        # number of dsitinct vertices \n        n = len(vertices)\n        disjoint_set = DisjointSet(n)\n    \n        for edge in edges:\n            disjoint_set.union(edge)\n            \n        return disjoint_set.cycle\n```\n\n\n### Overview \n\nThe ***key observation*** to sovling this problem is to recognize that the ***tree*** we are asked to find is actually a ***spanning tree***.\n\na ***spanning tree*** of an undirected graph ```G```  is a subgraph of ```G``` that is a ***tree*** , ***contains all vertices*** of ```G```, and has the ***minimum possible number of edges***. (we define a tree as an undirected graph with no cycles for this problem). \n\nObserve the following graph.\n\n![image](https://assets.leetcode.com/users/images/925b39df-f828-4c9b-bf95-2fefe0cbade1_1608864655.7227347.png)\n\nif we remove edge ```(1, 6)``` from the above graph, we get a spanning tree. becuase the graph is now ***acyclic*** (contains no cycles) , and still ***contains all vertices*** and does so with the ***minimum possible number of edges***. (their is more than one spanning tree for ```G``` this is just one).\n\n![image](https://assets.leetcode.com/users/images/d81c5645-e988-4894-854a-dfdf6c24438b_1608865847.9841955.png)\n\n\n ***Kruskal\'s Algorithm***  is a well known algorithm for finding the ***minimum cost spanning tree***. This problem is asking us to find the *minimum cost spanning tree* for the special case where all edge weights are```1``` and ties are broken by a predefined ordering. \n\n### Kruskal\'s Algorithm (Intuition) \n\nKruskal\'s is a greedy algoritm and says, start building a spanning tree by always taking the minimum cost edge, and keep going until all  ```n``` vertices are included.  \n\nif one keeps building our spanning tree in such a manner eventually we may choose an edge that results in a graph with a ***cycle***, in this event, do not include this edge in the ***spanning tree***.\n\nSince all edges in this problem have a weight of ```1```, take the edges in any order. Thus the order the edges are given will suffice. \n\n***Constructing the graph based on the order the edges are given...***\n\n![image](https://assets.leetcode.com/users/images/80fb9f1f-6998-40fc-bda0-aa8818da1844_1609012636.157277.png)\n\nAdding Edge ```(2, 3)``` in step 3 results in a cycle, thus it should not be included in the spanning tree. \n\nStep 2 in the diagram above is a minimum spanning tree, because it is an ***acyclic connected graph*** that includes all vertices with the ***minimum possible number of edges***. it is a minimum cost spanning tree because all edge weights added together have the lowest cost (there is an implicit weight of ```1```) there are other spanning trees with the same cost. any will suffice.  \n\n\n### Kruskals (Implementation)\n\nA [disjoint set data structure](https://en.wikipedia.org/wiki/Disjoint_sets) makes implementing kruskal\'s algorithm straightforward.\n\n\nbelow is a visual walkthrough of kruskal\'s using an array based disjoint set implementation for this graph\n\n![image](https://assets.leetcode.com/users/images/7268aa17-0899-4577-be95-b19f2bc437f5_1609107235.373219.png)\n\n\nHere is the walk through. \n\n![image](https://assets.leetcode.com/users/images/9c109e83-060a-4794-b615-6fb6b65476f7_1609106969.4191828.png)\n\nNote that if the graph contains more than one cycle, just continue in the same fashion keeping  track of the most recent cycle. the most recent cycle after all edges have been seen is the answer.\n\nFor an indepth of video walkthough of kruskals and disjoint sets \n[Disjoint Set](https://www.youtube.com/watch?v=wU6udHRIkcc&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=17)\n
['Union Find', 'Python']