MENU

洛谷P3367 【模板】并查集

洛谷P3367

最后得出的结果是find8(while非递归+按秩合并+秩和fa记在一个数组上)最快,当N较小时秩选用size,当N较大时秩选用depth。
当不方便非递归时可以写递归的(find6或find7)。
inline似乎没有明显优化。

对于各种并查集写法速度的研究

复赛前刷模板.jpg

#include<cstdio>
#include<cctype>
struct io {
    static const int L = (1 << 21) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    void putc(char X) {
        *oS++ = X;
        if(oS == oT)flush();
    }
    char gc() { return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin), (iS == iT ? EOF : *iS++)) : *iS++; }
    template<class T>T rd() {
        int c = gc();
        T X = 0;
        for(; !isdigit(c); c = gc());
        for(; isdigit(c); c = gc())X = X * 10 + (c & 15);
        return X;
    }
    template<class T>void print(T X) {
        if(!X) { putc('0'); return; }
        int tp = 0;
        for(; X; st[tp++] = X % 10 + 48, X /= 10);
        for(tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N = ip.rd<int>(), M = ip.rd<int>(), fa[10001];
inline int find(int X) { while(fa[X] >= 0 && fa[fa[X]] >= 0)X = fa[X] = fa[fa[X]]; return fa[X] < 0 ? X : fa[X]; }
int main() {
    for(int i = 1; i <= N; ++i)fa[i] = -1;
    while(M--) {
        int Z = ip.rd<int>(), X = ip.rd<int>(), Y = ip.rd<int>();
        switch(Z) {
            case 1:X = find(X), Y = find(Y);
                if(X != Y) {
                    if(fa[X] < fa[Y])fa[Y] = X;
                    else {
                        if(fa[X] == fa[Y])fa[Y]--;
                        fa[X] = Y;
                    }
                }
                break;
            case 2:ip.putc(find(X) == find(Y) ? 'Y' : 'N'), ip.putc('\n');
        }
    }
}
Leave a Comment

captcha
请输入验证码