self-studying-online

 Kruskal MST 模板： class UnionFind: def __init__ ( self , n ): self .parent = list ( range ( n )) self .rank = [ 0 ] * n def find ( self , x ): if self .parent[ x ] != x : self .parent[ x ] = self . find ( self .parent[ x ]) return self .parent[ x ] def union ( self , x , y ): root_x = self . find ( x ) root_y = self . find ( y ) if root_x == root_y: return if self .rank[root_x] < self .rank[root_y]: self .parent[root_x] = root_y elif self .rank[root_x] > self .rank[root_y]: self .parent[root_y] = root_x else : self .parent[root_y] = root_x self .rank[root_x] += 1 def kruskal ( n , edges ): edges . sort ( key = lambda edge : edge[ 2 ]) uf = UnionFind ( n ) mst_w = 0 mst_edges= [] for u, v, w in edges : if uf. find (u) != uf. find (v): uf. union (u, v) mst_w += w ...

并查集模板 class UnionFind: def __init__ ( self , n ): self .parent = [i for i in range ( n )] self .rank = [ 0 ] * n def find ( self , x ): if self .parent[ x ] != x : self .parent[ x ] = self . find ( self .parent[ x ]) return self .parent[ x ] def union ( self , x , y ): root_x = self . find ( x ) root_y = self . find ( y ) if root_x == root_y: return if self .rank[root_x] < self .rank[root_y]: self .parent[root_x] = root_y elif self .rank[root_x] > self .rank[root_y]: self .parent[root_y] = root_x else : self .parent[root_y] = root_x self .rank[root_x] += 1 n, m = map ( int , input (). split ()) uf = UnionFind (n) for _ in range (m): z, x, y = map ( int , input (). split ()) x -= 1 y -= 1 if z == 1 : uf. union (x, y) else : if uf. find (x) != uf. find (y): print ( 'N...