并查集

Disjoint-set data structure

主要思想就是合并和查询，对于并查集而言，判断无向图的连通分量个数，或者判断无向网中任何两个顶点是否连通。

• 合并（Union）:把两个不相交的集合合并为一个集合中

• 查询（Find）:查询两个元素是否在同一个集合中

  直接上优化算法

  // 按秩合并 通过减少层数来减少搜索次数
  void merge(int i, int j)
  {
  	i = find(i);
  	j = find(j);
  	if(i == j) return;
  	if(Rank[i] < Rank[j])
  		pre[i] = j;
  	else {
  		if(Rank[i] == Rank[j])
  			Rank[i]++;
  		pre[j] = i;
  	}
  }
  
  // 查询 路径压缩   递归
  int find(int x)
  {
  	if(fa[x] == x)
  		return x;
  	else {
  		fa[x] = find(fa[x])
  		reture fa[x];
  	}
  }
  
  // 查询 非递归优化
  int find(int x)
  {
  	int k, j , r;
  	r = x;
      k = x;
  	// 寻找总前驱
  	while(r != pre[r])
      	r = pre[r];
      // 路径压缩
      while(k != r)
      {
      	j = pre[k];
      	pre[k] = r;
      	k = j;
      }
      return r;
  }
  

  Leetcode--684 冗余连接

  class D{
  public :
  	vector<int> pre;
  	vector<int> Rank;
  	D(int n): pre(vector<int>(n+1)), Rank(vector<int>(n+1)) {
  		for(int i=1; i<=n ; i++)
  			pre[i] = i;
  	}
  	
  	int find(int x)
  	{
  		if(pre[x] == x)
  			return x;
  		else {
  			pre[x] = find(pre[x]);
  			return pre[x];
  		}
  	}
  	
  	bool merge(int i, int j)
  	{
  		i = find(i);
  		j = find(j);
          if(i == j) return true;
  		if(Rank[i] < Rank[j])
  			pre[i] = j;
  		else {
  			if(Rank[i] == Rank[j])
  				Rank[i]++;
  			pre[j] = i;
      	}
          return false;
  	}
  };
  class Solution {
  	public:
  	vector<int> findRedundantConnection(vector<vector<int>>& edges) {
  		int n = edges.size();
  		D d(n);
  		for (auto& e: edges) {
  			if(d.merge(e[0], e[1])) 
  				return {e[0] ,e[1]};
  		}
  		return {};
      }
  };