本文主要是介绍day56-graph theory-part06-8.26，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
tasks for today:
1. 108.冗余连接
2. 109.冗余连接II
---------------------------------------------------------------------------------
1. 108.冗余连接
in this practice, there is a rule needed to be identified: if u & v have been connected to a same root, then if a new couple come up, and isSame is true, there would be a circle showing up, which means this edge should be removed.
def find(u, father):if u == father[u]: return uelse: return find(father[u], father)def isSame(u, v, father):u = find(u, father)v = find(v, father)return u == vdef join(u, v, father):u = find(u, father)v = find(v, father)if u == v: returnfather[v] = udef main():n = int(input())father = list(range(0,n+1))for _ in range(n):s, t = map(int, input().split())if isSame(s, t, father):print(' '.join([str(s),str(t)]))return 0else:join(s, t, father)if __name__ == "__main__":main()2. 109.冗余连接II
the key difference in this practice is the direct requirement for the edge, the introduce more complicated operation in the main function.
def find(u, father):if father[u] == u:return uelse:return find(father[u], father)def isSame(u, v, father):u = find(u,father)v = find(v,father)return u == vdef join(u, v, father):u = find(u,father)v = find(v,father)if u == v: returnfather[v] = udef isTreeAfterRemove(edges, deleteedge, father):# print(type(edges))# print(edges)# for i, j in edges:# print(i,j)for s, t in edges:if s == edges[deleteedge][0] and t == edges[deleteedge][1]: continueif isSame(s, t, father):return False join(s, t, father)return Truedef getRemoveEdge(edges, father):for s, t in edges:if isSame(s, t, father):print(' '.join([str(s), str(t)]))returnjoin(s, t, father)def main():n = int(input())edges = []isDegree = [0] * (n+1)father = list(range(0, n+1))for _ in range(n):s, t = map(int, input().split())isDegree[t] += 1edges.append([s,t])suspect = []for i in range(n-1, -1, -1):if isDegree[edges[i][1]] == 2:suspect.append(i)# print(type(edges))# isTreeAfterRemove(edges, suspect[0], father)if len(suspect)>0:if isTreeAfterRemove(edges, suspect[0], father):print(' '.join(list(map(str, edges[suspect[0]]))))returnelse:print(' '.join(list(map(str, edges[suspect[1]]))))returngetRemoveEdge(edges, father)if __name__ == "__main__":main()
这篇关于day56-graph theory-part06-8.26的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
