ファインド

ユニオンファインド木の定義

グループ分けを管理するデータ構造です。

• Union：グループ同士を併合（へいごう）
• Find：ある要素がどのグループに属して（ぞくして）いるかを見つける

クラスカル法（Kruskal Algorithm）の一つ。

• 最小全域（ぜんいき）木問題をとくアルゴリズムの一つ。

---

①ファインド

ユニオンファインド木において、ある要素の根を求めること

• p は q の根である

using System;

class Program
{
    static int[] arr;
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        
        arr = new int[n];
        
        var line = Console.ReadLine().Split();
        
        for(int i = 0; i < n; i++){
            arr[i] = int.Parse(line[i]);
        }
        
        int x = int.Parse(Console.ReadLine());
        
        Console.WriteLine(Find(x));
    }
    
    static int Find(int x)
    {
        if (arr[x] == x)
        {
            return x;
        }
        else
        {
            return Find(arr[x]);
        }
    }
}