ACM算法竞赛三语言快速切换实用指南

前言

在ACM算法竞赛中，Java、C++和Python是最常用的三种编程语言。每种语言都有其独特的优势和适用场景，掌握快速切换技能能够显著提升解题效率。本指南将深入剖析三语言的核心差异，提供实用的切换策略和实战技巧。

1. 语言特性对比分析

1.1 执行效率对比

语言	编译方式	执行效率	内存占用	启动时间
C++	静态编译	最高	最低	最快
Java	JIT编译	中等	中等	中等
Python	解释执行	最低	最高	最慢

实际性能数据：

C++：O2优化下通常比Java快2-3倍，比Python快10-50倍
Java：JIT预热后性能接近C++，但内存占用约为C++的1.5-2倍
Python：CPython解释器下，简单循环操作比C++慢20-100倍

1.2 内存管理特性

C++内存管理

// 手动内存管理示例
int* arr = new int[1000000];  // 堆分配
// 使用完毕后必须手动释放
delete[] arr;

// RAII机制示例
class SmartArray {
    std::unique_ptr<int[]> data;
public:
    SmartArray(size_t n) : data(new int[n]) {}
    // 自动释放，无需手动delete
};

Java内存管理

// 自动垃圾回收
int[] arr = new int[1000000];  // 堆分配
// 无需手动释放，由GC自动处理

// 内存泄漏示例（避免）
List<Object> list = new ArrayList<>();
while (true) {
    list.add(new Object());  // 可能导致OOM
}

Python内存管理

# 自动引用计数 + 垃圾回收
arr = [0] * 1000000  # 列表自动管理内存

# 内存优化技巧
import gc
gc.collect()  # 手动触发垃圾回收

# 使用__slots__减少内存占用
class Node:
    __slots__ = ['value', 'next']  # 限制属性，减少内存
    def __init__(self, v):
        self.value = v
        self.next = None

1.3 语法特点分析

类型系统对比

特性	C++	Java	Python
类型检查	静态	静态	动态
泛型支持	模板	泛型	动态类型
自动类型推导	auto	var	天生动态
函数重载	支持	支持	不支持

代码简洁性对比

C++ Lambda表达式：

auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.first < b.first;
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

Java Lambda表达式：

1	PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

Python Lambda表达式：

1
2
3

import heapq
heap = []
heapq.heappush(heap, (priority, data))  # 最简洁

2. 数据结构与容器实现

2.1 数组与向量

C++ std::vector

#include <vector>
#include <algorithm>

// 动态数组操作
vector<int> arr;
arr.reserve(1000);  // 预分配内存，避免多次扩容
arr.push_back(10);
arr.emplace_back(20);  // C++11，更高效

// 二维数组
vector<vector<int>> matrix(n, vector<int>(m));

// 排序
sort(arr.begin(), arr.end(), greater<int>());

Java ArrayList

import java.util.*;

// 动态数组操作
List<Integer> arr = new ArrayList<>(1000);  // 指定初始容量
arr.add(10);

// 二维数组
int[][] matrix = new int[n][m];
List<List<Integer>> dynamicMatrix = new ArrayList<>();

// 排序
Collections.sort(arr, Collections.reverseOrder());

Python List

# 动态数组操作
arr = []
arr.append(10)

# 二维数组
matrix = [[0 for _ in range(m)] for _ in range(n)]

# 排序
arr.sort(reverse=True)

2.2 链表实现

C++链表

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 创建链表
ListNode* head = new ListNode(1);
head->next = new ListNode(2);

Java链表

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// 使用内置LinkedList
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(1);
list.addLast(2);

Python链表

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 创建链表
head = ListNode(1)
head.next = ListNode(2)

2.3 优先队列（堆）

C++优先队列

#include <queue>
#include <vector>

// 最大堆
priority_queue<int> max_heap;

// 最小堆
priority_queue<int, vector<int>, greater<int>> min_heap;

// 自定义比较器
struct Node {
    int val, priority;
    bool operator<(const Node& other) const {
        return priority > other.priority;  // 最小堆
    }
};
priority_queue<Node> pq;

Java优先队列

import java.util.*;

// 最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 自定义比较器
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

Python优先队列

import heapq

# 最小堆
heap = []
heapq.heappush(heap, 5)
heapq.heappop(heap)

# 最大堆技巧
max_heap = []
heapq.heappush(max_heap, -5)
actual_value = -heapq.heappop(max_heap)

# 元组堆
heapq.heappush(heap, (priority, data))

2.4 哈希表实现

C++哈希表

#include <unordered_map>
#include <unordered_set>

// 哈希映射
unordered_map<string, int> mp;
mp["key"] = 10;

// 哈希集合
unordered_set<int> st;
st.insert(5);

// 处理冲突
struct pair_hash {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        return hash<T1>()(p.first) ^ hash<T2>()(p.second);
    }
};
unordered_map<pair<int,int>, int, pair_hash> pair_map;

Java哈希表

import java.util.*;

// 哈希映射
Map<String, Integer> map = new HashMap<>();
map.put("key", 10);

// 哈希集合
Set<Integer> set = new HashSet<>();
set.add(5);

// 处理复杂键
Map<List<Integer>, Integer> listMap = new HashMap<>();

Python哈希表

# 字典
mp = {}
mp['key'] = 10

# 集合
st = set()
st.add(5)

# 复杂键处理
tuple_map = {}
tuple_map[(1, 2)] = 5  # 元组可作为键

2.5 树与图的表示

图的邻接表表示

C++实现：

#include <vector>
using namespace std;

// 无向图
vector<vector<int>> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);

// 加权图
struct Edge {
    int to, weight;
};
vector<vector<Edge>> adj_w(n);
adj_w[u].push_back({v, w});

Java实现：

import java.util.*;

// 无向图
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(v);
adj.get(v).add(u);

// 加权图
class Edge {
    int to, weight;
    Edge(int t, int w) { to = t; weight = w; }
}
List<List<Edge>> adj_w = new ArrayList<>();

Python实现：

# 无向图
adj = [[] for _ in range(n)]
adj[u].append(v)
adj[v].append(u)

# 加权图
adj_w = [[] for _ in range(n)]
adj_w[u].append((v, w))

3. 算法实现范式

3.1 递归算法实现

深度优先搜索（DFS）

C++版本：

void dfs(int u, vector<bool>& visited, const vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, visited, adj);
        }
    }
}

// 使用栈的非递归版本
void dfs_iterative(int start, const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    stack<int> st;
    st.push(start);
    
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        
        visited[u] = true;
        // 逆序压栈，保证顺序正确
        for (int i = adj[u].size() - 1; i >= 0; i--) {
            int v = adj[u][i];
            if (!visited[v]) st.push(v);
        }
    }
}

Java版本：

void dfs(int u, boolean[] visited, List<List<Integer>> adj) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            dfs(v, visited, adj);
        }
    }
}

// 非递归版本
void dfsIterative(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        
        visited[u] = true;
        // 逆序压栈
        List<Integer> neighbors = adj.get(u);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            int v = neighbors.get(i);
            if (!visited[v]) stack.push(v);
        }
    }
}

Python版本：

def dfs(u, visited, adj):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v, visited, adj)

# 非递归版本
def dfs_iterative(start, adj):
    visited = [False] * len(adj)
    stack = [start]
    
    while stack:
        u = stack.pop()
        if visited[u]:
            continue
            
        visited[u] = True
        # 逆序压栈
        for v in reversed(adj[u]):
            if not visited[v]:
                stack.append(v)

# 使用yield的生成器版本
def dfs_generator(u, adj):
    visited = [False] * len(adj)
    stack = [u]
    
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            yield node
            for neighbor in reversed(adj[node]):
                if not visited[neighbor]:
                    stack.append(neighbor)

3.2 动态规划实现

背包问题（0/1背包）

C++版本：

int knapsack(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w-weights[i-1]] + values[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

// 空间优化版本
int knapsack_optimized(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
        }
    }
    return dp[W];
}

Java版本：

int knapsack(int W, int[] weights, int[] values) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = Math.max(dp[i-1][w], 
                                   dp[i-1][w-weights[i-1]] + values[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

// 空间优化版本
int knapsackOptimized(int W, int[] weights, int[] values) {
    int n = weights.length;
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
        }
    }
    return dp[W];
}

Python版本：

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

# 空间优化版本
def knapsack_optimized(W, weights, values):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
    return dp[W]

# 使用装饰器记忆化
from functools import lru_cache

def knapsack_recursive(W, weights, values):
    n = len(weights)
    
    @lru_cache(maxsize=None)
    def dfs(index, remaining_weight):
        if index == n or remaining_weight == 0:
            return 0
        
        if weights[index] > remaining_weight:
            return dfs(index + 1, remaining_weight)
        
        return max(dfs(index + 1, remaining_weight),
                  dfs(index + 1, remaining_weight - weights[index]) + values[index])
    
    result = dfs(0, W)
    dfs.cache_clear()  # 清理缓存
    return result

3.3 贪心算法实现

活动选择问题

C++版本：

struct Activity {
    int start, end;
    bool operator<(const Activity& other) const {
        return end < other.end;  // 按结束时间排序
    }
};

int activitySelection(vector<Activity>& activities) {
    sort(activities.begin(), activities.end());
    
    int count = 1;
    int last_end = activities[0].end;
    
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= last_end) {
            count++;
            last_end = activities[i].end;
        }
    }
    return count;
}

Java版本：

class Activity {
    int start, end;
    Activity(int s, int e) { start = s; end = e; }
}

int activitySelection(Activity[] activities) {
    Arrays.sort(activities, (a, b) -> a.end - b.end);
    
    int count = 1;
    int lastEnd = activities[0].end;
    
    for (int i = 1; i < activities.length; i++) {
        if (activities[i].start >= lastEnd) {
            count++;
            lastEnd = activities[i].end;
        }
    }
    return count;
}

Python版本：

def activity_selection(activities):
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    
    count = 1
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:
            count += 1
            last_end = end
    return count

# 更Pythonic的实现
from operator import itemgetter

def activity_selection_pythonic(activities):
    activities.sort(key=itemgetter(1))
    
    count, last_end = 0, 0
    for start, end in activities:
        if start >= last_end:
            count += 1
            last_end = end
    return count

4. 快速切换技巧

4.1 语法速查对照表

基本语法对照

功能	C++	Java	Python
输入	`cin >> x;`	`x = sc.nextInt();`	`x = int(input())`
输出	`cout << x;`	`System.out.println(x);`	`print(x)`
数组	`int a[100];`	`int[] a = new int[100];`	`a = [0] * 100`
循环	`for(int i=0;i<n;i++)`	`for(int i=0;i<n;i++)`	`for i in range(n):`
条件	`if(x>0)`	`if(x>0)`	`if x>0:`
函数	`int add(int a,int b)`	`int add(int a,int b)`	`def add(a, b):`

容器操作对照

容器	C++	Java	Python
栈	`stack<int> s; s.push(x);`	`Stack<Integer> s = new Stack<>(); s.push(x);`	`s = []; s.append(x); s.pop()`
队列	`queue<int> q; q.push(x);`	`Queue<Integer> q = new LinkedList<>(); q.offer(x);`	`from collections import deque; q = deque(); q.append(x)`
优先队列	`priority_queue<int> pq;`	`PriorityQueue<Integer> pq = new PriorityQueue<>();`	`import heapq; heapq.heappush(heap, x)`

4.2 常见算法实现差异

二分查找实现

C++版本：

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Java版本：

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 使用内置函数
int index = Arrays.binarySearch(arr, target);

Python版本：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 使用bisect模块
import bisect
index = bisect.bisect_left(arr, target)

4.3 调试技巧对比

调试工具使用

C++调试：

// 使用cerr进行调试输出
#include <iostream>
using namespace std;

cerr << "Debug: x = " << x << endl;

// 条件编译调试
#ifndef ONLINE_JUDGE
    #define DEBUG(x) cerr << #x << " = " << x << endl
#else
    #define DEBUG(x)
#endif

Java调试：

// 使用System.err进行调试输出
System.err.println("Debug: x = " + x);

// 使用断言
assert x > 0 : "x must be positive";

Python调试：

# 使用print调试
print(f"Debug: x = {x}", file=sys.stderr)

# 使用logging模块
import logging
logging.basicConfig(level=logging.DEBUG)
logging.debug(f"x = {x}")

# 使用pdb调试器
import pdb; pdb.set_trace()

5. 实战建议

5.1 语言选择标准

根据题目特点选择语言

选择C++的场景：

时间限制严格的题目（<1秒）
需要高精度计算的数学题
需要位运算优化的题目
内存使用要求严格的题目

选择Java的场景：

需要处理大整数（BigInteger）
需要丰富的数据结构支持
代码可读性要求高的题目
需要字符串处理的题目

选择Python的场景：

算法验证和快速原型开发
字符串处理复杂的题目
需要高级数据结构（如Counter、defaultdict）
代码量要求少的题目

5.2 混合使用技巧

多语言协作策略

策略1：Python验证 + C++实现

先用Python快速实现算法验证正确性
将关键部分用C++重写以获得性能

示例流程：

# 步骤1：Python验证算法
import sys
sys.setrecursionlimit(100000)

# 快速验证思路

// 步骤2：C++高性能实现
#include <bits/stdc++.h>
using namespace std;
// 优化后的实现

策略2：Java库函数 + 自定义算法

// 使用Java内置数据结构
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 使用Java的TreeSet处理有序集合
        TreeSet<Integer> set = new TreeSet<>();
    }
}

5.3 竞赛专用模板

C++竞赛模板

#include <bits/stdc++.h>
using namespace std;

#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) x.begin(), x.end()

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LLINF = 1e18;

// 快速输入输出模板
template<typename T>
void read(T& x) {
    x = 0; T f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x *= f;
}

template<typename T>
void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    fastIO;
    // 主程序逻辑
    return 0;
}

Java竞赛模板

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }
        
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try { str = br.readLine(); }
            catch (IOException e) { e.printStackTrace(); }
            return str;
        }
    }
    
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        // 主程序逻辑
    }
}

Python竞赛模板

import sys
import math
from collections import *
from functools import *
from itertools import *
import bisect
import heapq

def solve():
    # 快速输入
    input = sys.stdin.readline
    
    # 主程序逻辑
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 输出结果
    print(result)

if __name__ == "__main__":
    solve()

5.4 性能优化清单

编译优化选项

C++编译优化：

# OJ通常使用
-O2 -std=c++17

# 本地调试使用
-g -O0 -std=c++17

Java编译优化：

1 2	# 使用JIT优化 -server -Xmx1024m

Python优化：

# 使用PyPy加速
pypy3 solution.py

# 使用Cython加速
# 需要额外配置

6. 实战案例分析

6.1 最短路径问题（Dijkstra算法）

问题描述

给定带权有向图，求单源最短路径。

三语言实现对比

C++高效实现：

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

vector<int> dijkstra(int start, const vector<vector<pii>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Java实现：

import java.util.*;

class Edge {
    int to, weight;
    Edge(int t, int w) { to = t; weight = w; }
}

int[] dijkstra(int start, List<List<Edge>> adj) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    
    dist[start] = 0;
    pq.offer(new int[]{0, start});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        
        if (d > dist[u]) continue;
        
        for (Edge e : adj.get(u)) {
            int v = e.to, w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

Python实现：

import heapq

def dijkstra(start, adj):
    n = len(adj)
    dist = [float('inf')] * n
    dist[start] = 0
    
    heap = [(0, start)]
    
    while heap:
        d, u = heapq.heappop(heap)
        
        if d > dist[u]:
            continue
            
        for v, w in adj[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    return dist

6.2 并查集实现对比

三语言实现

C++实现：

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

Java实现：

class UnionFind {
    private int[] parent;
    private int[] rank;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

Python实现：

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, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        
        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
        return True

# 使用字典的并查集（处理动态节点）
class UnionFindDict:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0
        
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]