集計(union find)のまとめ

(一)概念

検索セットの基本的な概念はブログを参照してください.https://www.cnblogs.com/xzxl/p/7226557.html

（二）用途

接続の問題を効率的に解決

迷宮

マルチノードの接続状態

集合クラスの実装

（三）共通テンプレート

3つの要素:

各ノードの親ノード

を記録する必要がある.

各ノードの祖先ノード

を見つける

2 2 2つのノードの祖先ノードを

にマージ
コード:

public class Template {
    int[] pre;
    
    public void init(int len){ // pre 
        pre = new int[len];
        for(int i=0;i

(四)例題を精選する

(1)Leetcode 547 Friend Circles
标题:現存するN人の生徒、生徒と生徒の間にはモーメンツが存在し、AがBの友人、BがCの友人であれば、A、B、Cは同じモーメンツの中で、現在NxNの行列Aが与えられており、A[i][j]=1はiとjが友人であることを表していると考えられる.全部で何人のモーメンツがありますか?
入力:A=[[1,1,0],[1,1,0],[0,0,1]]出力:2入力:A=[[1,1,0],[1,1,1],[0,1,1]]出力:1

public class Friend_Circles_547 {
    public class UnionFind{
        int[] pre; // x pre[x]
        int count;
     
        public void init(int n){
            pre = new int[n];
            for(int i=0;i

(2)Leetcode 684 Redundant Connection
題意:図を表す配列Aが与えられ、A[i]=[u,v]はノードu,vの間にエッジが存在することを表す.この図(自体がツリーではない)が1つのエッジだけを削除することでツリーになることを確認します.削除したエッジを見つけて、複数ある場合は、配列の最後に現れたエッジを返してください.
入力:A=[[1,2],[1,3],[2,3]]出力:[2,3]入力:A=[[1,2],[2,3],[1,4],[1,4],1,5]]出力:[1,4]

public class Redundant_Connection_684 {
    public class UnionFind{
       int[] pre;
        public void init(int len){
            pre = new int[len+5];
            for(int i=0;i

(3)Leetcode 959 Regions Cut By Slashes
題意:1つのNxNの行列が与えられ、行列は1 x 1の小格子からなり、各小格子には'/','','の3つのケースが含まれ、行列中の連通領域を返すことができる.
入力:A=["/","/"]出力:2入力:A=["/","/"]出力:4

public class Regions_Cut_By_Slashes_959 {
    
    public class UnionFind{
        int[] pre;
        
        public void init(int len){ // 4 , 
            pre = new int[len*len*4];
            for(int i=0;i= 0)
                    uf.union(root + 0, (root - 4 * n) + 3);
                // east west
                if (j + 1 < n)
                    uf.union(root + 2, (root + 4) + 1);
                if (j - 1 >= 0)
                    uf.union(root + 1, (root - 4) + 2);
            }
        }
        for (int x = 0; x < 4 * n * n; x++) {
            if (uf.find(x) == x)
                res++;
        }
        return res;
    }
}

(4)Leetcode 765 Couples Holding Hands(後)
N組の夫婦がランダムに2*N席に座っていて、今すべての夫婦が手をつないで(隣接すればいい)、私たちはいくつかの人の席を交換して、少なくとも何回交換しなければ問題を満たすことができないかを聞く必要があります.夫婦は数字を使って、(0,1)は夫婦、(2,3)は夫婦であると推す.ヒント:最大30組の夫婦が存在します.