基础

What is a Union-Finding?

• It is a data structure

• A data structure

When?

• 解决图问题

• use case：图是在动态变化

Why?

• 代码极其短

• hit use case 时间复杂度

关注点

• 两个集合是不是联通

• 集合==》联通力量

• 性质：每一个集合都有一个代表

思考方式

• 集合代表着帮派

• 集合的代表元素代表帮派老大

API

• UnionFind() constructor 构造函数O(n), n as number of node

• union(int a, int b):把a加入b的集合，或者把b加入a的集合

• int find(a):找到a所在集合的代表元素

时间复杂度

• Quick Union -- union find

  • find: O(n)

  • union: O(n)

• Quick Find -- union find

  • find: O(1)

  • union: O(n)

• Weighted/Ranked/OtherRanked Union Find(Tree Array Based)

  • find: O(log n)

  • union O(log n)

• Weight Union Find with Path Compression

  • find: O*(1)

  • union: O*(1)

  • where *: O(loglog(n)) > O(1)

How

• Union - Find用数组实现的数据结构

• 假设长度是n -> int[] laoda

• laoda[i] 代表i的老大是谁

• count：一共有多少个帮派

• int[] size -> size[i] 代表i所在的帮派有多少

How: Union Find底板（2min！！！）

class UnionFind{
    int[] laoda; //有几个帮派的老大, 可能是需要laodaMap map<你的类型，帮派的老大>
    int[] size; //几个帮派的大小
    int count;
    public UnionFind(int n){
        this.laoda = new int[n];
        this.size = new int[n];
        this.count = n;
        for (int i =; i< n; i++) {
            laoda[i] = i;
            size[i] = 1;
        }
    }
    public int find(int a) {
    
    }
    public void union(int a, int b) {
    
    }
    


}

UF时空复杂度

• union,find 都是O*(1)

• constructor: both O(n)

面试里注意点的和基本逻辑

• 对于find(a):找到的是真老大

• union(a, b): a,b 要先检查需不需要union，如果老大都一样，就不需要用union了

第一种Union-Find: Quick Union

union(a, b)--> 把a加入b

• example:

  • laoda: {0, 1, 2},

  • union(2, 1),

  • laoda = {0,1,1}

  • union(1, 0)

  • laoda: {0, 0, 1}

  • 其实0，1，2，都在一个联通分量里面，但是观察老大是分级别的

• 谁是真老大？

  • 真老大的特点laoda[zhenlaoda] = zhenlaoda

• quick union:

  • union 一时爽，find的时候要溯源

public int find(int a) { //这个是用来找真正的老大，就是前面提到的溯源
    while (a != laoda[a]) {
        a = laoda[a];
    }
    return a;
}
public void union(int a, int b){//注意这里是把a加入b
    int alaoda = find(a);
    int blaoda = find(b);
    if (alaoda == blaoda) return;
    laoda[a] = b;
    count--;
    size[blaoda] += size[alaoda];
}

TC&SC:

• find: O(n)

• union: O(n)

第二种Union Find: Quick Find

Find O(1)

example:

• laoda: {0, 1, 2},

• union(2, 1),

• laoda = {0,1,1}

• union(1, 0)

• laoda: {0, 0, 1} ==> {0,0,0}

• 操作上来说，如果要把a的老大改成c，不能只改a，把所有以a为老大的小弟们的老大都改成c（相当于老板跳槽，把他所有学生都带去跳槽）

public int find(int a) {
    return laoda[a];
}
public void union(int a, int b) {
    int alaoda = find(a);
    int blaoda = find(b);
    for (int i = 0; i < laoda.length; i++) { // 把a里面所有的都变成b
        if (laoda[i] = a) {
            laoda[i] = b;
        }
    }
    if (alaoda == blaoda) return;
    laoda[a] = b;
    count--;
    size[blaoda] += size[alaoda];
}

TC& SC: Find(1), Union(n)

第三种Union- Find, Weight Union Find => Tree

核心思想：

• union(a,b)刚才是a加入b，or b加入a

• 现在一定是小的那个，加入大的那个大小: size[i]

• 是用tree的形式，越靠近tree的顶，越是那个大的

• example

• 

public int find(int a) {
    while(a != laoda[a]) {
        a = laoda[a];
    }
    return a;
}
public void union(int a, int b) {
    int alaoda = find(a);
    int blaoda = find(b);
    if (alaoda == blaoda) return;
    if (size[alaoda] >= size[blaoda]) {
        laoda[blaoda] = alaoda // 不是laoda[b] = a; 
        size[alaoda] += size[blaoda];
    }
    else{
        laoda[alaoda] = blaoda;
        size[blaoda] += size[alaoda];
    }
}

• 这里相当于size是weight

第四种Union-Find：Weighted Union FInd with PathCompression

• Path Compression：路径压缩

• 路径压缩精髓：苟富贵勿相忘(一个人富贵了，所有帮助给你的人全都浮过)

• example

• 

//细节版本
public int find(int a) {
    //自己得先富贵了，真的找到真老大
    int zhenlaoda = a;
    while (laoda[zhenlaoda] != zhenlaoda) {
        zhenlaoda = laoda[zhenlaoda];
    }
    //什么都没有做，但是至少知道了真老大是谁，可以帮别人；
    int 每一次帮你的人 = a;
    while (每一次帮你的人 != zhenlaoda) {
        每一次帮你的人 = laoda[a];  // 记录爷爷的节点是谁
        laoda[a] = zhenlaoda;
        a = 每一次帮你的人;
    }
    return zhenlaoda;
}

public void union(int a, int b) {
    int alaoda = find(a);
    int blaoda = find(b);
    if (alaoda == blaoda) return;
    if (size[alaoda] >= size[blaoda]) {
        laoda[blaoda] = alaoda; //!!注意这里！！
        size[alaoda] += size[blaoda];
    }else {
        laoda[alaoda] = blaoda;
        size[blaoda] += size[alaoda];
    }
}

其他版本，Pure Recursion Implementation

step1 : function 的定义

• int fnd(a): 给我一个点a可以找到a所在的帮派

step 2: base case

• laoda[a] = a return a

step 3: subproblem

• find(laoda[a]) 这个子问题return的结果的人其实就是zhenlaoda

step 4 recursion rule

• laoda[a]上面的点已经路径压缩完了

• 真老大不就是子问题retun的结果了么？

• laoda[a] = zhenlaoda

• return zhenlaoda

//pure recursion
public int find(int a) {
    inf (laoda[a] == a) {
        return a;
    }
    int zhenlaoda = find(laoda[a]);
    laoda[a] = zhenlaoda;
    return zhenlaoda;
}

//更简化版本
public int find(int a) {
    return laoda[a] = a == laoda[a]? a: find(laoda[a]);
}

面试简化版本

class UnionFind{
    int[] laoda;
    public UnionFind(int n) {
        this.laoda = new int[n];
        for(int i = 0; i < n; i++) {
            laoda[i] = i;
        }
    
    }
    public int find(int a) {
        return laoda[a] = a == laoda[a]? a: find(laoda[a]);
    }
    
    public void union(int a , int b) {
        int alaoda = find(a);
        int blaoda = find(b)l
        if (alaoda = blaoda) return;
        if (size[alaoda] >= size[blaoda]) {
            laoda[blaoda] = alaoda;
            size[alaoda] += size[blaoda];
        }else {
            laoda[alaoda] = blaoda;
            size[blaoda] += size[alaoda];
        }
    }
}

多加一个getMaxSetLaoda

class UnionFind{
    int[] laoda;
    int[] size;
    public UnionFind(int n) {
        this.laoda = new int[n];
        this.size = new int[n];
        for(int i = 0; i < n; i++) {
            laoda[i] = i;
            size[i] = i;
        }
    }
    public int find(int a) {
        return laoda[a] = a == laoda[a]? a: find(laoda[a]);
    }
    
    public void union(int a , int b) {
        int alaoda = find(a);
        int blaoda = find(b)l
        if  realMaxLaoda = find(maxLaoda);
        
        
        if (size[alaoda] >= size[blaoda]) {
            laoda[blaoda] = alaoda;
            size[alaoda] += size[blaoda];
            if (size[alaoda] > size[realMaxLaoda]) {
                maxLaoda = alaoda;
            }
        }else {
            laoda[alaoda] = blaoda;
            size[blaoda] += size[alaoda];
            if (size[blaoda]> size[realMaxLaoda]) {
                maxLaoda = blaoda;
            }
        }
    }
    public int getMAxSetLaoda() {
        return maxLaoda;
    }
}

add a method findMax()

• add a method findMax() to the union-find data type so that findMax(i) returns the largest element in the connected component containing i.

• 对于UF实现上的follow up怎么做？思考徐亚激素哪些新的field，然后改变union(95%) + find(5%)更新他们

class UnionFind{
    int[] laoda;
    int[] size;
    int[] max; //每个联通分量里面最大的
    public UnionFind(int n) {
        this.laoda = new int[n];
        this.size = new int[n];
        this.max = new int[n];
        for(int i = 0; i < n; i++) {
            laoda[i] = i;
            size[i] = i;
            max[i] = i;
        }
    }
    public int find(int a) {
        return laoda[a] = a == laoda[a]? a: find(laoda[a]);
    }
    
    public void union(int a , int b) {
        int alaoda = find(a);
        int blaoda = find(b)l
        if  (alaoda == blaoda) return;
        
        
        if (size[alaoda] >= size[blaoda]) {
            laoda[blaoda] = alaoda;
            size[alaoda] += size[blaoda];
            max[alaoda] = Math.max(max[alaoda], max[blaoda]);
        }else {
            laoda[alaoda] = blaoda;
            size[blaoda] += size[alaoda];
            max[alaoda] = Math.max(max[alaoda], max[blaoda]);
        }
    }
    public int getMaxSetLaoda() {
        return maxLaoda;
    }
}