并查集


#include <stdio.h>
#define maxn 100
typedef int bool;

int N, M;
int up[maxn+1];

FILE *in;

int root(int i)
{
    // version 2
    return (up[i]==i)?i:(up[i]=root(up[i]));

    // version 1
    // if(up[i]==i)
    //     return i;
    // else {
    //     up[i] = root(up[i]);
    //     return up[i];
    // }
}
bool same(int i, int j) { return root(i) == root(j); }
void merge(int i, int j)
{
    // version 2
    if((i=root(i))!=(j=root(j))) up[i]=j;

    // version 1
    // i = root(i);
    // j = root(j);
    // if(i!=j) up[i]=j;
}

void Input() {
    int i;
    in = fopen("0.in", "r");
    fscanf(in, "%d%d", &N, &M);
}

void Print() {
    int i;
    for(i=1; i<=N; ++i) {
        printf("up[%d]=%d\n", i, up[i]);
    }
}

void Init() {
    int i;
    for(i=1; i<=N; ++i) {
        up[i] = i;
    }
}

void Work() {
    int i, x, y;
    char op[10];
    for(i=1; i<=M; ++i) {
        fscanf(in, "%s%d%d", op, &x, &y);
        if(op[0]=='m') {
            merge(x, y);
        } else {
            printf("%s\n", same(x, y)?"yes":"no");
        }
//        Print();
    }
    fclose(in);
}

int main() {
    Input();
    Init();
    Work();
    return 0;
}