pypy3 解法, 执行用时: 865ms, 内存消耗: 41776K, 提交时间: 2023-07-05 22:51:08

p = list(range(30001))  # 将每个值与自己对应
cnt = [1 for _ in range(30001)]
val = [0 for _ in range(30001)]


def dfs(x):  # 并查集
    if p[x] != x:
        temp = p[x]
        p[x] = dfs(p[x])
        val[x] += val[temp]
    return p[x]


for _ in range(int(input())):
    op = input().split()
    if op[0] == 'M':
        x = int(op[1])
        y = int(op[2])
        y = dfs(y)
        x = dfs(x)
        p[x] = y
        val[x] = cnt[y]
        cnt[y] += cnt[x]
    else:
        x = int(op[1])
        t = dfs(x)
        print(val[x])

Python3 解法, 执行用时: 1051ms, 内存消耗: 6760K, 提交时间: 2023-05-24 16:51:41

p = list(range(30001))
cnt = [1 for _ in range(30001)]
val = [0 for _ in range(30001)]
def find(x):
    if p[x] != x:
        temp = p[x]
        p[x] = find(p[x])
        val[x] += val[temp]
    return p[x]

q = int(input())
for i in range(q):
    op = input().split()
    if op[0] == 'M':
        x = int(op[1])
        y = int(op[2])
        y = find(y)
        x = find(x)
        p[x] = y
        val[x] = cnt[y]
        cnt[y] += cnt[x]
    else:
        x = int(op[1])
        t = find(x)
        print(val[x])

C++(clang++ 11.0.1) 解法, 执行用时: 225ms, 内存消耗: 1960K, 提交时间: 2022-09-02 12:52:56

#include <bits/stdc++.h>

using namespace std;

int a[30004], b[30004], c[30004];
int find(int x) { return a[x]==x?x:(a[0]=find(a[x]),c[x]+=c[a[x]],a[x]=a[0],a[x]);}
int main() {
    int q, x, y;
    char ch;
    cin >> q;
    for(int i=1;i<=30000;i++) a[i] = i, b[i] = 1;
    while(q--) {
        cin >> ch >> x;
        if(ch=='M') cin >> y, x = find(x), y= find(y), a[x] = y, c[x] = b[y], b[y] += b[x];
        else find(x), cout << c[x] << endl;
    }
}