难度：困难

题目：

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 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

Related Topics

• 深度优先搜索

• 广度优先搜索

• 并查集

• 图

重点！！！解题思路

第一步：

明确解题手段
类似于此种连通性问题均能使用并查集来实现
但是这题我们需要将并查集稍微修改一下
已知此题要求每个节点的入度不能大于1
所以我们需要在并查集中添加一个记录每个几点入度的数组

第二步：

题中要求返回最后出现的答案，那么我就从后往前进行枚举
每次选中的不进行判断，
如果在这种情况下，其余节点全部连接成功并且没有连成一个环，并且每个节点的入度不>1
那么这次选中的数组则为多余值，
这个值即为答案

源码：

class UnionFind {//记录每个节点的根节点int[] parent;//记录每个子集的节点数int[] rank;//记录并查集中的联通分量数量int count;//每个节点的入度数量int[] vis;//是否有环boolean flag1;//是否入度大于1boolean flag2;public UnionFind(int n){count=n;parent=new int[n];for (int i=0;i=0 ; i--) {int x=edges[i][0];int y=edges[i][1];UnionFind uf = new UnionFind(edges.length+1);for (int j=0;j1){ //每次让下标为1的节点入度+1uf.flag2=true;break;}}if (!uf.flag1&& !uf.flag2){ //如果没成环，入度也是正常的，那么此次选中的待删除节点即为答案return new int[]{x,y};}}return null; //这里返回什么都可以，因为上面一定会返回一个值}
}

运行结果：

如果您还有什么疑问或解答有问题，可在下方评论，我会及时回复。

系列持续更新中，点个订阅吧