心路历程：
最开始的想法是把环给破开就行，思路：建图，遍历找环，然后找到edges里属于环的一个边；每次不选择上一步走过的边，DFS，需要回溯。后来查阅资料发现这道题适合用一个叫并查集的数据结构。之前自己做美团的笔试题的时候，就遇到了类似朋友圈的问题但是没做出来。
并查集的核心是将同一’圈子‘的结点都连接到一个’老大‘身上，可以一直串联，也可以为了降低下次查询的复杂度而利用图的秩将其合并。
注意的点
1、这道题可以顺序建立并查集，当建立到第一个闭环集合时，证明此时成环，从题目要求中发现只多一个边，那么这个最后增加的边就是最后多余的边。
2、rank秩的作用是降低find复杂度，并不是必须的。
3、本题的技巧在于可以通过判断成环的最后一笔来找出冗余的边，判断成环的一个方法就是并查集在union操作时两个father是一个（不需要连接）。
解法一：并查集
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# 就是把环给破开就行
# 思路：建图，遍历找环，然后找到edges里属于环的一个边；每次不选择上一步走过的边，DFS,需要回溯
# 并查集：如何根据边的关系建立图？->建立指向同一个father的集合即可
n = len(edges)
uf = UF(n)
for x, y in edges:
if uf.union(x, y) == 0: return [x,y]
class UF:
def __init__(self, n):
self.father = [i for i in range(n+1)] # 因为图中结点是1开头的，所以第0位置让出去了
def find(self, x):
if x == self.father[x]: return x # 找到了父节点，父节点是一直没有变过的初始化就有的结点
return self.find(self.father[x])
def union(self, x, y):
fx, fy = self.find(x), self.find(y)
if fx == fy: return 0 # 证明不需要连接
# 默认前面的是father
self.father[fy] = fx
return 1
解法二：压缩路径的并查集
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# 并查集：如何根据边的关系建立图？->建立指向同一个father的集合即可
n = len(edges)
uf = UF(n)
for x, y in edges:
if uf.union(x, y) == 0: return [x,y]
class UF:
def __init__(self, n):
self.father = [i for i in range(n+1)] # 因为图中结点是1开头的，所以第0位置让出去了
self.rank = [1]*(n+1) # 表示从父结点到最远子结点的距离
def find(self, x):
if x == self.father[x]: return x # 找到了父节点，父节点是一直没有变过的初始化就有的结点
return self.find(self.father[x])
def union(self, x, y):
fx, fy = self.find(x), self.find(y)
if fx == fy: return 0 # 证明不需要连接
# 下面这段是用于压缩路径的；树的秩大的当爹，一样大的时候就指定一个，然后将其秩+1
rfx, rfy = self.rank[fx], self.rank[fy]
if rfx > rfy: self.father[fy] = fx
elif rfx < rfy: self.father[fx] = fy
else:
self.father[fy] = fx
self.rank[fx] += 1
return 1
