[LeetCode]Redundant Connection

无向图是否有环的问题，N个节点，如果是数的话一定需要N-1的边并且是所有节点都是连通的。如果再加一条边，一定会形成环。问题也就转换成无向图找环的问题。和Graph Valid Tree是一样的。DFS的找环做法显然是可以行的，remove找到环的时候当前边就行。连接性的问题用Union Find也是非常好的思路，比如Kruskal Algorithm找Minimum Spanning Tree的时候就是用Union Find来check加上当前边会不会形成环。这一题我们可以用一样的思路。用Union Find比DFS好的一点是我们不需要事先建图，只需要每次处理当前边就可以了。关于Union Find的介绍可以参考这篇文章，代码如下：