并查集 Union-Find

				
					
					1
					// 并查集：森林 + 父指针
				
			
				
					
					2
					function find(x):
				
			
				
					
					3
					  if parent[x] != x:
				
			
				
					
					4
					    parent[x] = find(parent[x])   // 路径压缩
				
			
				
					
					5
					  return parent[x]
				
			
				
					
					6
					 
				
			
				
					
					7
					function union(x, y):
				
			
				
					
					8
					  rx = find(x); ry = find(y)
				
			
				
					
					9
					  if rx == ry: return
				
			
				
					
					10
					  // 按秩合并：小树挂大树
				
			
				
					
					11
					  if rank[rx] < rank[ry]: parent[rx] = ry
				
			
				
					
					12
					  else: parent[ry] = rx
				
			
				
					
					13