luogu P 1551親戚(そして入門を調べます)

これは一つのテンプレートです.
話して探してみます.私もまだ覚えたばかりですが、.
検索セットは、ツリー構造のデータ構造であり、主に2つの非交差セットを結合するために使用される.
まず初期化です.f配列は第i点の父を表します.

for(int i=1;i<=n;i++)f[i] = i;

そして、検索集は合併と検索に分けられています.私はmerge(合併)と書くのが慣れています.
統合するなら、まずQery関数を呼び出して2点の祖先ノードを調べます.同じ祖先でなければ、2つの集合は関係がありません.その後、祖先ノードが代表する集合を統合します.

void merge(int x,int y){

    int f1 = query(x);

    int f2 = query(y);

    if(f1 != f2){

        if(rand()%2)f[f1] = f2;

        else f[f2] = f1;

    }

    return;

}

次はqueryです.父のノードを再帰的に調べて、祖先のノードを見つけるまでは、後は経路圧縮です.道のすべての点を探している祖先ノードは同じですから、帰る時は毎回同じセットに入れます.検索時間を大幅に短縮できます.書いて調べたら、必ずパスを持って圧縮されます.カードの経路が圧縮されている問題があるようです.dalaoから聞いただけです.具体的な問題は具体的に分析してください.

int query(int x){

    if(x == f[x])return x;

    else return f[x] = query(f[x]);//    

}

次はこの問題です.つまり、一つの問題を調べてテーマによってすればいいです.
テーマの背景
ある家族が大きすぎると、親戚かどうかを判断するのは難しいです.今はある親戚関係図を提出して、任意の二人が親戚関係を持っているかどうかを求めています.
テーマの説明
xとyは親戚で、yとzは親戚です.xとzも親戚です.x、yが親戚ならxの親戚はyの親戚です.yの親戚もxの親戚です.
入出力フォーマット
入力フォーマット:
第一行:三つの整数n、m、p、(n<=5000、m<=5000、p<=5000)、それぞれn人がいることを表して、m個の親戚関係、pが親戚関係に対して聞く.
以下のm行:各行の2つの数Mi、Mj、1<=Mi、Mj<=Nは、MiとMjが親戚関係を持っていることを表しています.
次のp行:各行の2つの数Pi、Pjは、PiとPjが親戚関係を持っているかどうかを尋ねます.
出力フォーマット:
P行、各行に一つの’Yes’または’No’があります.i番目の質問の答えは「持っています」または「持っていません」という親戚関係です.
入出力の例
サンプルを入力します.
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
出力サンプル例钾1:コピー
はい
はい
No.
ACコードを添付:

#include
#include
#include
#include
#include

using namespace std;
const int maxn = 500521;
int n,m,p;
int mi;
int mj;
int pi;
int pj;
int f[maxn];
inline int read(){//    
    int x=0;int f=1;char c=getchar();
    while(c'9'){
        if(c=='-')f=-f;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
} 
int query(int x){//    
    if(x == f[x])return x;
    else return f[x] = query(f[x]);//    
}
void merge(int x,int y){//    
    int f1 = query(x);
    int f2 = query(y);
    if(f1 != f2){
        if(rand()%2)f[f1] = f2;
        else f[f2] = f1;
    }
    return;
}
int main(){
    n = read();
    m = read();
    p = read();
    for(int i=1;i<=n;i++)f[i] = i;//   ，   
    for(int i=1;i<=m;i++){
        mi = read();
        mj = read();
        merge(mi,mj);
    }
    for(int i=1;i<=p;i++){
        pi = read();
        pj = read();
        if(query(pi) == query(pj)){
            printf("Yes
");
        }
        else printf("No
");
    }
    
    return 0;
}