算法

(并查集) $O(m)$

并查集模版题，这里需要写路径压缩，不然时间复杂度是$O(nm)$，肯定过不了。

C++ 代码

#include <iostream>

using namespace std;

struct unionFind
{
    int bin[10005];

    unionFind()
    {
        for(int i=1;i<=10002;i++)
            bin[i]=i;
    }

    int anc(int x)
    {
        if(x == bin[x]) return x;
        return bin[x] = anc(bin[x]); // 实现路径压缩 
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
    void ask(int x,int y)
    {
        cout << ("%s\n",anc(x)==anc(y)?"Y\n":"N\n");
    }
};

unionFind u;

int main() {
    int n, m, z, x, y;
    cin >> n >> m;

    while (m--) {
        cin >> z >> x >> y;
        if (z == 1) u.uni(x, y);
        else u.ask(x, y);
    }

    return 0;
}