TIOJ 1833 . Problem B 陽炎眩亂

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

int fat[100001];

void init(int n){

    for(int lx = 0;lx < n;lx++)

        fat[lx] = lx;

    return;

}

int gfat(int a){

    return (fat[a] == a) ? a : fat[a] = gfat(fat[a]) ;

}

void join(int a, int b){

    int fa = gfat(a);

    int fb = gfat(b);

    fat[fb] = fa;

    return;

}

int main(){

    int n, q; scanf("%d %d", &n, &q);

    init(n);

    char buf[100];

    while(q--){

        scanf("%s", buf);

        if(buf[0] == 'M'){

            int a, b; scanf("%d %d", &a, &b);

            join(a-1, b-1);

        }else{

            int a; scanf("%d", &a);

            printf("%d\n", gfat(a-1)+1);

        }

    }

    return 0;

}