《藍橋杯每日一題》并查集·AcWing1249. 親戚

1.題目描述

或許你并不知道，你的某個朋友是你的親戚。

他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子。

如果能得到完整的家譜，判斷兩個人是否是親戚應該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那麼檢驗親戚關系實非人力所能及。

在這種情況下，最好的幫手就是計算機。

為了将問題簡化，你将得到一些親戚關系的資訊，如Marry和Tom是親戚，Tom和Ben是親戚，等等。

從這些資訊中，你可以推出Marry和Ben是親戚。

請寫一個程式，對于我們的關于親戚關系的提問，以最快的速度給出答案。

輸入格式

輸入由兩部分組成。

第一部分以 N,M 開始。N 為問題涉及的人的個數。這些人的編号為 1,2,3,…,N。下面有 M 行，每行有兩個數 ai,bi，表示已知 ai 和 bi是親戚。

第二部分以 Q開始。以下 Q 行有 Q 個詢問，每行為 ci,di，表示詢問 ci 和 di 是否為親戚。

輸出格式

對于每個詢問 ci,di，輸出一行：若 ci和 di 為親戚，則輸出“Yes”，否則輸出“No”。

資料範圍

1≤N≤20000

1≤M≤10的六次方

1≤Q≤10的六次方

輸入樣例：

10 7

2 4

5 7

1 3

8 9

1 2

5 6

2 3

3

3 4

7 10

8 9

輸出樣例：

Yes

No

Yes

2.思路分析

我們先初始化p數組

然後輸入m個數

我們查詢一下，如果root1(find(a),即a的根節點)不是root2(find(b),即b的根節點)，我們就把它們連接配接起來

最後輸入q個數判斷一下就行了，如果它們都是一個祖宗，我們就輸出Yes，反之輸出No

注意用BufferedReader和BufferedWriter優化一下輸入輸出，不然會逾時

關于快速輸入可以看一下我的這篇部落格

https://blog.csdn.net/m0_68055637/article/details/128551437

3.Ac代碼

import java.io.*;

public class Main {
    static int N=20010;
    static int []p=new int[N]; //存儲每個點的祖宗節點

    public static void main(String[] args) throws IOException {
        BufferedReader  br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter  bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String []s=br.readLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
        for (int i = 0; i < n; i++) {
            p[i]=i;
        }
        while (m-->0){
            s=br.readLine().split(" ");
        int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]);
        int root1=find(a),root2=find(b); //分别找到兩個人的祖宗節點，并判斷是不是親戚
        if(root1!=root2)  p[root1]=root2;      //如果不是，添加至同族
        }
        int t=Integer.parseInt(br.readLine());
        while (t-->0){
            s=br.readLine().split(" ");
            int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]);
            bw.write(find(a)==find(b)?"Yes":"No");
            bw.newLine(); //換行
        }
        bw.flush();  //輸出緩沖區才能輸出
    }

    private static int find(int x) {
        if(p[x]!=x)  p[x]=find(p[x]);
        return p[x];
    }
}
           

感謝你能看完， 如有錯誤歡迎評論指正，有好的思路可以交流一波，如果對你有幫助的話，點個贊支援下