并查集一个比较少用的数据结构。关于并查集的通俗解释可以参考文章:

超有爱的并查集

并查集的功能

原图来自花花酱

  1. Find(x):find the root of x
  2. Union(x,y):merger two node

然而并查集需要做到find的时间复杂度为O(1),显然直接递归是无法实现。那么就需要路径压缩!

并查集路径压缩(Path compression)

路径压缩发生在find执行中。当find(x)时,若x不是root,则向上递归时,依次把x往上挂,直到挂到root上,这样下次找x时,都是O(1)。

并查集联合

两个(或多个簇)联合需要引入另一个变量rank,可当做是权重。这个权重是根节点的权重,类比理解为:我的树下面节点多、复杂,路径压缩时间更多,因此我的rank高。下次合并时,rank低的要挂到rank高的上。即rank低的root节点父节点指向rank高的root!

并查集的实现

代码引自花花酱(需fq)

// Author:Nkul
class UnionFindSet{
    /**
        并查集通常用节点ID表示节点
        parents_数组记录当前节点的上级节点!如parents_[1]=3表示1节点上级节点为3。显然parents_[i]=i表示i节点就是root节点!
    */
    private int[] parents_;
    private int[] ranks_;


    //构造函数
    public UnionFindSet(int n){
        parents_=new int[n+1];
        ranks_=new int[n+1];
        for(int i=0;i<parents_.length;i++){
            parents_[i]=i;
            ranks_[i]=1;
        }
    }
    public int Find(int u){
        while(parents_[u]!=u){
            /**
                比如p[2]=3,此时2节点的上级是3,为了找到2节点的root节点,我们先要找到3的上级,即p[p[2]];
            */
            parents_[u]=parents_[parents_[u]];
            u=parents_[u];
        }
        return u;
    }
    public boolean Union(int u,int v){
        /**
            查找root节点
        */
        int pu=Find(u);
        int pv=Find(v);

        /**
            同属一个簇,不用合并
        */
        if (pu==pv) {
            return false;
        }
        /**
            ranks_低的簇挂到高的簇下
        */
        if(ranks_[pv]>ranks_[pu])
            parents_[pu]=pv;
        else if(ranks_[pu]>ranks_[pv])
            parents_[pv]=pu;
        else{
            parents_[pv]=pu;
            ranks_[pu]+=1;
        }
        return true;
            
    }
}

"""
Author: Huahua
"""
class UnionFindSet:
    def __init__(self, n):
        self._parents = [i for i in range(n + 1)]
        self._ranks = [1 for i in range(n + 1)]
    
    def find(self, u):
        while u != self._parents[u]:
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u
    
    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv: return False
        
        if self._ranks[pu] < self._ranks[pv]:
            self._parents[pu] = pv
        elif self._ranks[pu] > self._ranks[pv]:
            self._parents[pv] = pu
        else:        
            self._parents[pv] = pu
            self._ranks[pu] += 1
        
        return True

// Author: Huahua
class UnionFindSet {
public:
    UnionFindSet(int n) {
        ranks_ = vector<int>(n + 1, 0);        
        parents_ = vector<int>(n + 1, 0);                
        
        for (int i = 0; i < parents_.size(); ++i)
            parents_[i] = i;
    }
    
    // Merge sets that contains u and v.
    // Return true if merged, false if u and v are already in one set.
    bool Union(int u, int v) {
        int pu = Find(u);
        int pv = Find(v);
        if (pu == pv) return false;
        
        // Meger low rank tree into high rank tree
        if (ranks_[pv] < ranks_[pu])
            parents_[pv] = pu;           
        else if (ranks_[pu] < ranks_[pv])
            parents_[pu] = pv;
        else {
            parents_[pv] = pu;
            ranks_[pu] += 1;
        }
        
        return true;
    }
    
    // Get the root of u.
    int Find(int u) {        
        // Compress the path during traversal
        if (u != parents_[u])
            parents_[u] = Find(parents_[u]);        
        return parents_[u];
    }
private:
    vector<int> parents_;
    vector<int> ranks_;
};

LeetCode上关于并查集(Union_Find)问题

399.除法求值

399.除法求值

本题有两种解法,第一种DFS后续再说。第二种:

A/B=2--->记为p[A]={B,2.0} 即A=B*2.0

class Solution {

    // 新建类 保存并查集的元素
    class Node {
    public String parent;
    public double ratio;
    public Node(String parent, double ratio) {
      this.parent = parent;
      this.ratio = ratio;
    }
  }
  
  class UnionFindSet {

    private Map<String, Node> parents = new HashMap<>();
    
    public Node find(String s) {
      if (!parents.containsKey(s)) return null;
      Node n = parents.get(s);
      if (!n.parent.equals(s)) {
        Node p = find(n.parent);
        n.parent = p.parent;
        n.ratio *= p.ratio;
      }
      return n;
    }
    
    public void union(String s, String p, double ratio) {
      boolean hasS = parents.containsKey(s);
      boolean hasP = parents.containsKey(p);

      // merge时,分四种情况
      //1、簇里均没有两个节点s=p*ration
      if (!hasS && !hasP) {
        parents.put(s, new Node(p, ratio));
        parents.put(p, new Node(p, 1.0));
      } 
      //只有s节点,p=s* (1/ration)
      else if (!hasP) {
        parents.put(p, new Node(s, 1.0 / ratio));
      } else if (!hasS) {
        parents.put(s, new Node(p, ratio));
      } 
      //已经在簇里面了
      else {
        Node rS = find(s);
        Node rP = find(p);
        rS.parent = rP.parent;
        rS.ratio = ratio / rS.ratio * rP.ratio;
      }
    }
  }


    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        UnionFindSet u = new UnionFindSet();
    
    for (int i = 0; i < equations.size(); ++i)
      u.union(equations.get(i).get(0), equations.get(i).get(1), values[i]);
    
    double[] ans = new double[queries.size()];
    
    for (int i = 0; i < queries.size(); ++i) {      
      Node rx = u.find(queries.get(i).get(0));
      Node ry = u.find(queries.get(i).get(1));
      if (rx == null || ry == null || !rx.parent.equals(ry.parent))
        ans[i] = -1.0;        
      else
        ans[i] = rx.ratio / ry.ratio;
    }
    
    return ans;

    }
}

547.朋友圈

547.朋友圈
相较上一题,本题比较简单,即最基本的并查集!



class Solution {

    //base UnionFindSet
    class UnionFindSet{
        public int[] p;
        public int[] rank;
        public UnionFindSet(int n){
            p=new int[n+1];
            rank=new int[n+1];
            for(int i=0;i<p.length;i++){
                p[i]=i;
                rank[i]=1;
            }
        }
        public int find(int u){
            while(p[u]!=u){
                p[u]=p[p[u]];
                u=p[u];
            }
            return u;
        }

        public boolean union(int u,int v){
            int pu=find(u);
            int pv=find(v);
            if(pu==pv) return false;
            if(rank[pu]>rank[pv]){
                p[pv]=pu;
            }else if(rank[pv]>rank[pu]){
                p[pu]=pv;
            }else{
                p[pu]=pv;
                rank[pv]++;
            }
            return true;
        }
    }
    public int findCircleNum(int[][] M) {
        int n=M.length;
        UnionFindSet u=new UnionFindSet(n);

        //create unionfindset
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                // if is friend,merge
                if(M[i][j]==1) u.union(i,j);
            }
        }

        Set<Integer> set=new HashSet<>();

        //find root of node
        for(int i=0;i<n;i++){
            set.add(u.find(i));
        }
        return set.size();

    }
}

684.冗余连接

684.冗余连接



class Solution {
    class UF{
        public int[] p;
        public int[] r;
        public UF(int n){
            p=new int[n+1];
            r=new int[n+1];
            for(int i=0;i<n+1;i++){
                p[i]=i;
                r[i]=1;
            }
        }
        public int find(int u){
            while(p[u]!=u){
                p[u]=p[p[u]];
                u=p[u];
            }
            return u;
        }
        public boolean union(int v,int u){
            int pv=find(v);
            int pu=find(u);
            if(pv==pu) return false;
            if(r[pv]<r[pu]){
                p[pv]=pu;
            }else if(r[pu]<r[pv]){
                p[pu]=pv;
            }else{
                p[pu]=pv;
                r[pv]++;
            }
            return true;
        }
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n=edges.length;
        UF uf=new UF(n);
        for(int[] edge:edges){
            // once 2 edge has same root,it means this 2 node has another edges to contact,so this is redundant
            if(!uf.union(edge[0],edge[1]))
                return edge;
        }
        return null;

    }
}

Last modification:April 21st, 2020 at 01:57 am