[LeetCode]Redundant Connection II

和之前题目不一样的是这道题目变成了有向图。那么变为有向图之后，我们对directed tree加上一条边和undirected tree有什么区别呢。可能会有以下三种状况：

1. 仍然存在环，比如[1, 2], [2,3], [3,1]
2. 不存在环但是存在某一个节点有两个父节点，比如[2,1], [3,1], [2, 3]
3. 1和2的情况同时存在，比如[2,1], [3,1], [1,4], [4,2]

所以和I的解法不同，这里每一种情况我们都要判断并删除相应的边，具体算法如下：

1. 如果是情况1，根据题目的要求，我们删除边e。e满足条件，按照题目给定的边的顺序依次加上边，当加上e的时候，第一次出现环
2. 如果是情况2，删除一条通向v的边。v满足条件其有两个父节点。e满足条件其在题目给定的边的顺序中比另外一条通向v的边出现较后
3. 如果是情况3，删除一条通向v的边。v满足条件其有两个父节点。e满足条件其在环上

我们只需要对这三种情况分别处理即可，DFS显然可以解，我们只需要记录环的路径（如果存在）和拥有两个父节点的v的对应的入射边（如果存在）。然后对于以上三种情况分别处理。但是DFS的解法需要我们建图。和I一样，我们可以用Union Find，这样省去了建图的步骤更为效率。在Union Find中我们也要对环和拥有两个父节点的v分别记录然后根据以上算法处理。关于Union Find的介绍可以参考这篇文章。代码如下：

	class Solution {
	public:
	vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
	int n = edges.size();
	m_uf = vector<int>(n + 1, 0);
	m_sz = vector<int>(n + 1, 1);
	m_parent = vector<int>(n + 1, -1);
	for(int i = 0; i <= n; ++i)
	m_uf[i] = i;
	//first check if there is node with two parents
	vector<vector<int>> culprits;
	for(auto& e : edges)
	{
	int from = e[0], to = e[1];
	if(m_parent[to] != -1)
	{
	culprits.push_back({m_parent[to], to});
	culprits.push_back(e);
	}
	m_parent[to] = from;
	}
	//check circle
	for(auto& e : edges)
	{
	int from = e[0], to = e[1];
	if(culprits.size() && to != culprits[0][1])
	connect(from, to);
	else if(culprits.empty())
	{
	if(find(from, to))
	return e;
	connect(from, to);
	}
	}
	if(find(culprits[0][0], culprits[0][1]))
	return culprits.front();
	else
	return culprits.back();
	}
	private:
	vector<int> m_uf;
	vector<int> m_sz;
	vector<int> m_parent;
	int root(int i)
	{
	if(m_uf[i] == i)
	return i;
	int r = root(m_uf[i]);
	m_uf[i] = r;
	return r;
	}
	void connect(int i, int j)
	{
	int ri = root(i), rj = root(j);
	if(ri != rj)
	{
	if(m_sz[ri] >= m_sz[rj])
	{
	m_uf[rj] = ri;
	m_sz[ri] += m_sz[rj];
	}
	else
	{
	m_uf[ri] = rj;
	m_sz[rj] += m_sz[ri];
	}
	}
	}
	bool find(int i, int j)
	{
	return root(i) == root(j);
	}
	};

view raw Redundant Connection II.cpp hosted with ❤ by GitHub