本文共 1251 字，大约阅读时间需要 4 分钟。

题目描述

给出一个并查集，请完成合并和查询操作。

输入格式:

第一行包含两个整数N、M，表示共有N个元素和M个操作。

输出格式:

如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

输入样例

4 7

输出样例

N

数据规模

对于30%的数据，N<=10，M<=20；

对于70%的数据，N<=100，M<=1000；

对于100%的数据，N<=10000，M<=200000。

时空限制：1000ms, 128M

注：PAT上有同样的题目，但是时空限制为400 ms, 64 MB

// 这个题目400ms的要求稍有严苛了，最后一个测试点时过时不过，不知道是否有更好的方法进行优化#include 
   
    using namespace std;int f[10005];int n, m;// // 递归find根节点// int find(int v)// {//     return f[v] == v ? v : f[v] = find(f[v]);// }// 非递归find根节点int find(int x){    int r = x;    while (r != f[r])        r = f[r];    int i = x, j;    while (i != r)    {        j = f[i];        f[i] = r;        i = j;    }    return r;}int main(){    // 清除cin效率问题    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    cin >> n >> m;    // init function    for (int i = 1; i <= n; i++)    {        f[i] = i;    }    while (m--)    {        int x, y, z;        cin >> x >> y >> z;        if (x == 1)        {            // merge function            f[find(y)] = find(z);        }        else        {            cout << (find(y) == find(z) ? "Y" : "N") << endl;        }    }    system("pause");    return 0;}
   

转载地址：http://bznaf.baihongyu.com/