算法工程师第四十八天（108.冗余连接 109.冗余连接II）

本文主要是介绍算法工程师第四十八天（108.冗余连接 109.冗余连接II），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考文献 代码随想录

一、冗余连接

题目描述

树可以看成是一个图（拥有 n 个节点和 n - 1 条边的连通无环无向图）。 

现给定一个拥有 n 个节点（节点标号是从 1 到 n）和 n 条边的连通无向图，请找出一条可以删除的边，删除后图可以变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例

3
1 2
2 3
1 3

输出示例

1 3

提示信息

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

数据范围：

1 <= N <= 1000.

问题分析

这道题目也是并查集基础题目。

这里我依然降调一下，并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。

如果还不了解并查集，可以看这里：并查集理论基础

我们再来看一下这道题目。

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。

如果有多个答案，则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如图所示：

节点A 和节点 B 不在同一个集合，那么就可以将两个 节点连在一起。

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

如图所示：

已经判断 节点A 和 节点B 在在同一个集合（同一个根），如果将 节点A 和 节点B 连在一起就一定会出现环。

这个思路清晰之后，代码就很好写了。

class UnionFind():def __init__(self, length):self.fa = list(range(length + 1))  # 初始化，默认自己为自己的父亲def find(self, x):if x != self.fa[x]: self.fa[x] = self.find(self.fa[x])  # 路基压缩return self.fa[x]def is_same(self, u, v):return self.find(u) == self.find(v)  # 查def join(self, u, v):fa_u = self.find(u)fa_v = self.find(v)  # 并if fa_v != fa_u:self.fa[fa_u] = fa_v# 不要形成环
n = int(input())
uf = UnionFind(n)
for i in range(n):u, v = map(int, input().split())if uf.is_same(u, v):print(u, v)else:uf.join(u, v)

二、冗余连接II

题目描述

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图： 

现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。 

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

输入示例

3
1 2
1 3
2 3

输出示例

2 3

提示信息

在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3

数据范围：

1 <= N <= 1000.

# 有向图要构成树有两个条件
# 1。每个节点入度必须为1
# 2。不可以形成环
# 删除一条边没有形成环，删除最后一边(情况1)
# 删除一条边以后可能形成环，必须判断（情况2）
# 本身可能是环，需要删除（情况3）
class Union_search:def __init__(self, M):self.father = [i for i in range(M + 1)]def find(self, u):if u != self.father[u]:self.father[u] = self.find(self.father[u])return self.father[u]def is_same(self, u, v):f_u = self.find(u)f_v = self.find(v)return f_u == f_vdef join(self, u, v):f_u = self.find(u)f_v = self.find(v)if f_u != f_v:self.father[f_v] = f_udef find_cycle(M, sides):  # 删除环us = Union_search(M)for x, y in sides:if us.is_same(x, y):  # 如果在同一个集合里return x, yus.join(x, y)return Nonedef is_cycle_after_remove(M, del_side, sides):us = Union_search(M)  # 初始化， m是边for x, y in sides:if x == del_side[0] and y == del_side[1]:  # 如果等于我们要删除的那条边的话，就跳过continueif us.is_same(x, y):  # 如果删除del_side之后，还存在环那么，直接返回Truereturn Trueus.join(x, y)    # 不存在环return False  # 删除了之后，不存在环def main():M = int(input())sides = []  # 存放的是边in_degree = [0] * (M + 1)for i in range(M):sides.append(list(map(int, input().split())))in_degree[sides[i][1]] += 1  # 统计每个节点的入度情况# 倒叙遍历入度为2的点，并将进入这些点的边加入vecvec = []for i in range(M - 1, -1, -1):  # 倒序遍历if in_degree[sides[i][1]] == 2:   # 统计出入度为2的是哪些边vec.append(sides[i])if vec:# 正序遍历vec列表，试图删除for i in range(len(vec)):if not is_cycle_after_remove(M, vec[i], sides):  # M是节点数量， vec[i]那些边参与入度为2的节点，然后删除的是靠后的那条边print(vec[i][0], vec[i][1])returnelse:# 如果没有找到可删除的边，试图验证是否形成环？x, y = find_cycle(M, sides)print(x, y)if __name__ == "__main__":main()

这篇关于算法工程师第四十八天（108.冗余连接 109.冗余连接II）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---