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)