题目

据说最多通过6个人就可以认识世界上的所有人。

小J和小R想知道，朋友关系具有可传递性——只要可以通过多人相互认识，就认为他们是朋友。小R不断告诉小J谁和谁互相认识，同时不定期询问谁和谁是否认识，请注意一个人和自己一定是朋友。

输入：第一行两个整数 q、n，q 表示询问次数，n 表示总人数。接下来 q 个询问：操作编号 a 及 x、y；a 为 1 表示 x、y 互相认识；a 为 2 表示查询 x、y 是否认识。
输出：对于每个操作 2，认识输出 YES，不认识输出 NO。

样例1：

输入

5 5
1 1 2
1 3 4
2 1 3
2 3 5
2 3 4

输出

NO
NO
YES

样例2：

输入

5 6
1 1 2
1 2 3
2 1 3
1 4 5
2 1 6

输出

YES
NO

思路

用并查集维护朋友关系：初始每个人的 parent 指向自己；合并时让 x 的根认 y 的根为老大；查询时比较两人的根是否相同。find 使用路径压缩（parent[x] = find(parent[x])），将沿途节点直接指向根，避免链式退化导致超时。

C++ · p43.cpp 
#include<bits/stdc++.h>
using namespace std;

int parent[100001];

int find(int x){
    if(parent[x]==x) return x;
    return parent[x]=find(parent[x]);
}

void unite(int x,int y){
    parent[find(x)]=find(y);
}

int main(){
    int q,n;
    cin>>q>>n;
    for(int c=1;c<=n;c++)
        parent[c]=c;
    for(int c=0;c<q;c++){
        int a,x,y;
        cin>>a>>x>>y;
        if(a==1){
            unite(x,y);
        }else if(a==2){
            if(find(x)==find(y))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

复杂度分析

  • 时间复杂度：O(q · α(n))，α 为反阿克曼函数，路径压缩后近似 O(1)。
  • 空间复杂度：O(n)，parent 数组。
今日感受

并查集的思路不难，但光会基本实现还不够——不加路径压缩直接 TLE。parent[x] = find(parent[x]) 这一行，找根的同时把沿途节点全部压平，是并查集能跑满分的关键。

← 返回菜鸟的coding