代码随想录算法训练营第五十六天 | 108.冗余连接 109.冗余连接II

108.冗余连接

题目链接：108. 冗余的边

文章讲解：代码随想录

思路： 题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树，如果有多个答案，则返回二维数组中最后出现的边。

从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点），如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

主函数判断一下边的两个节点在不在同一个集合就可以了

109.冗余连接II

题目链接：109. 冗余的边II

文章讲解：代码随想录

思路： 

有一个有向图，是由一颗有向树 + 一条有向边组成的（所以此时这个图就不能称之为有向树），现在让找到那条边把这条边删了，让这个图恢复为有向树。

有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。

情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了

情况二，只能删特定的一条边

入度为2的点需要判断删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边

情况三： 如果没有入度为2的点，说明图中有环了（注意是有向环），对于情况三，删掉构成环的边就可以了。

​​​​​​​