P2661 信息传递(并查集，python）

本文主要是介绍P2661 信息传递(并查集，python），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

原题

2. 题解

并查集找最小环。
使用 path_count 来计算节点和父亲节点的距离。

#!/usr/bin/env python
# encoding=utf-8
def init_parents(N):parents = {}path_count = {}for i in range(N):parents[i+1] = i+1path_count[i+1] = 0return parents, path_countdef find_parent(parents, path_count, x):if x != parents[x]:tmp = parents[x]parents[x] = find_parent(parents, path_count,parents[x])path_count[x] += path_count[tmp]return parents[x]def union(parents, path_count,  x, y):root_x = find_parent(parents, path_count,x)root_y = find_parent(parents, path_count,y)if root_x == root_y:return Trueelse:parents[root_x] = root_ypath_count[x] = path_count[y]+1return Falsedef min_time_count(N, edge):# 1. 初始化parents, path_count = init_parents(N)graph = list(zip([i+1 for i in range(N)], edge))#print(graph)# 2. 合并:min_count = float("inf")for edge in graph:x, y = edge[0],edge[1]if not union(parents, path_count, x, y):#print(graph, parents, path_count)continueelse:# 节点和父亲节点的距离，在加上父亲节点。tmp = abs(path_count[x] - path_count[y]) + 1min_count = min(min_count,tmp)#print(graph, parents, path_count)return min_countif __name__ == "__main__":# n = 5# T = [2,4,2,3,1]n = int(input())T = list(map(int, input().strip().split()))res = min_time_count(n,T)print(res)

这篇关于P2661 信息传递(并查集，python）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---