[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的介绍可以参考这篇文章，代码如下：

	class Solution {
	public:
	vector<int> findRedundantConnection(vector<vector<int>>& edges) {
	int n = edges.size();
	vector<int> uf(n + 1, 0);
	vector<int> sz(n + 1, 1);
	for(int i = 1; i <= n; ++i)
	uf[i] = i;
	for(auto& e : edges)
	{
	if(find(uf, e[0], e[1]))
	return e;
	else
	connect(uf, sz, e[0], e[1]);
	}
	return {};
	}
	private:
	int root(vector<int>& uf, int i)
	{
	if(i == uf[i])
	return i;
	int r = root(uf, uf[i]);
	uf[i] = r;
	return r;
	}
	void connect(vector<int>& uf, vector<int>& sz, int i, int j)
	{
	int ri = root(uf, i), rj = root(uf, j);
	if(sz[ri] >= sz[rj])
	{
	uf[rj] = ri;
	sz[ri] += sz[rj];
	}
	else
	{
	uf[ri] = rj;
	sz[rj] += sz[ri];
	}
	}
	bool find(vector<int> uf, int i, int j)
	{
	return root(uf, i) == root(uf, j);
	}
	};

view raw Redundant Connection.cpp hosted with ❤ by GitHub