?题目描述
在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
示例 1：
输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]
示例 2：
输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]
提示：
??? n == edges.length
??? 3 <= n <= 1000
??? edges[i].length == 2
??? 1 <= ui, vi <= n
?算法分析
方法一：并查集
思路与算法
在一棵树中，边的数量比节点的数量少 1。如果一棵树有 N 个节点，则这棵树有 N?1条边。这道题中的图在树的基础上多了一条附加的边，因此边的数量也是 N。
树中的每个节点都有一个父节点，除了根节点没有父节点。在多了一条附加的边之后，可能有以下两种情况：
??? 附加的边指向根节点，则包括根节点在内的每个节点都有一个父节点，此时图中一定有环路；
??? 附加的边指向非根节点，则恰好有一个节点（即被附加的边指向的节点）有两个父节点，此时图中可能有环路也可能没有环路。
要找到附加的边，需要遍历图中的所有的边构建出一棵树，在构建树的过程中寻找导致冲突（即导致一个节点有两个父节点）的边以及导致环路出现的边。
具体做法是，使用数组 parent记录每个节点的父节点，初始时对于任何 1≤i≤N都有 parent[i]=i，另外创建并查集，初始时并查集中的每个节点都是一个连通分支，该连通分支的根节点就是该节点本身。遍历每条边的过程中，维护导致冲突的边和导致环路出现的边，由于只有一条附加的边，因此最多有一条导致冲突的边和一条导致环路出现的边。
当访问到边 [u,v]时，进行如下操作：
??? 如果此时已经有 parent[v]≠v，说明 vvv 有两个父节点，将当前的边 [u,v]记为导致冲突的边；
??? 否则，令 parent[v]=u，然后在并查集中分别找到 u和 v的祖先（即各自的连通分支中的根节点），如果祖先相同，说明这条边导致环路出现，将当前的边 [u,v]记为导致环路出现的边，如果祖先不同，则在并查集中将 u 和 v进行合并。
根据上述操作，同一条边不可能同时被记为导致冲突的边和导致环路出现的边。如果访问到的边确实同时导致冲突和环路出现，则这条边被记为导致冲突的边。
在遍历图中的所有边之后，根据是否存在导致冲突的边和导致环路出现的边，得到附加的边。
如果没有导致冲突的边，说明附加的边一定导致环路出现，而且是在环路中的最后一条被访问到的边，因此附加的边即为导致环路出现的边。
如果有导致冲突的边，记这条边为 [u,v]，则有两条边指向 v，另一条边为 [parent[v],v]，需要通过判断是否有导致环路的边决定哪条边是附加的边。
??? 如果有导致环路的边，则附加的边不可能是 [u,v]因为 [u,v]已经被记为导致冲突的边，不可能被记为导致环路出现的边），因此附加的边是 [parent[v],v]。
??? 如果没有导致环路的边，则附加的边是后被访问到的指向 v的边，因此附加的边是 [u,v]。
代码
class Solution {
public:
vector<int> parents;
vector<int> ranks;
void Init(int n) {
parents.resize(n);
ranks.resize(n, 1);
for(int i = 0; i < n; ++i) {
parents[i] = i;
}
}
int find(int x) {
return x == parents[x]? x : parents[x] = find(parents[x]);
}
bool merge(int i, int j) {
int iroot = find(i);
int jroot = find(j);
if(iroot == jroot) {
return false;
}
if(ranks[iroot] <= ranks[jroot]) {
parents[iroot] = jroot;
} else {
parents[jroot] = iroot;
}
if(ranks[iroot] == ranks[jroot] && iroot != jroot) {
ranks[jroot]++;
}
return true;
}
bool checkCircle(vector<vector<int>>& edges, int index) {
int n = edges.size();
Init(n+1);
for(int i = 0; i < n; ++i) {
if(i == index) {
continue;
}
if(!merge(edges[i][0],edges[i][1])) { //合并失败，有环
return true;
}
}
return false;
}
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> in(n+1, 0);
bool in2 = false;
int index;
for(auto& edge : edges) {
in[edge[1]]++;
}
// 删除入度为2的边
for(int i = n-1; i >= 0; --i) {
if(in[edges[i][1]] == 2) {
if(!checkCircle(edges, i)) { //如果没有环，则入度为2的边就是删除的边
return edges[i];
}
}
}
// 删除入度为1的边，题目要求最后出现的，逆序遍历
for(int i = n-1; i >= 0; --i) {
if(in[edges[i][1]] == 1) {
if(!checkCircle(edges, i)) { // 如果没有环，则入度为1的边就是删除的边
return edges[i];
}
}
}
return vector<int>{};
}
};
时间复杂度分析
时间复杂度：O(Nlog?N)，其中 N是图中的节点个数。需要遍历图中的 N条边，对于每条边，需要对两个节点查找祖先，如果两个节点的祖先不同则需要进行合并，需要进行 2次查找和最多 1次合并。一共需要进行 2N次查找和最多 N次合并，因此总时间复杂度是 O(2Nlog?N)=O(Nlog?N)。这里的并查集使用了路径压缩，但是没有使用按秩合并，最坏情况下的时间复杂度是 O(Nlog?N)，平均情况下的时间复杂度依然是 O(Nα(N)，其中 α为阿克曼函数的反函数，α(N)\可以认为是一个很小的常数。
空间复杂度：O(N)，其中 N是图中的节点个数。使用数组 parent记录每个节点的父节点，并查集使用数组记录每个节点的祖先。
|