Java算法——并查集

川长思鸟来 2023-01-11 09:07 174阅读 0赞

# 功能 #

并查集是管理多个集合的算法，其功能包括集合的合并、集合内或集合间的查询。

# 背景 #

在中国古代，人们都比较重视血缘传承，几乎每家都至少会有一个男孩，后人总会牢记自己的祖先，这样就有了家谱 / 族谱。根据家谱 / 族谱，可以将后面几代人通过祖先的祖先都联系起来，使大家千万年前都是一家人。

现在有一个问题，如果每个人都只记得自己的爹，那么如何快速判断任意两个人，是否来自同一祖先呢？

# 输入示例 #

第一行两个整数 n m ，家谱共有n个人，编号从1 ~ n  
接下来m行，每行俩数i j，i 是 j 的儿子，i, j ∈ \[1，n\]  
最后一行，俩数 a b ，问a、b是否来自同一祖先

7  6
    3  1
    6  2
    7  3
    5  2
    4  1
    2  1
    6  7

# 输出示例 #

如果a、b来自同一祖先，输出true，否则输出false

true

# 分析 #

每个爹可能有不止一个儿子，也可能一个儿子也没有  
顶级祖先不再有爹  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDY5NA_size_16_color_FFFFFF_t_70_pic_center]  
我们用上面树（有向图）的形式直观表示一个家谱，如果想要判断 6 号和 7 号是否为一家人，那么就要先从一方起，逐步向上追查，一直追溯到顶级祖先，记为 x，然后再追查另一个人的顶级祖先，记为 y，如果x == y，二者为一家人。

如果直接构建树（有向图）恐怕有些复杂，你得先知道祖先是谁，然后从祖先出发，寻找与祖先直接相关的儿子，然后再分别以这些儿子为起点，再次搜索。单单是构建的过程花销就很大，因此不推荐。

下面采用并查集的方式解决此类问题。

# 方式一 #

直链式 “并”查集。

首先开辟一个n+1长度的数组，用于容纳 1 ~ n号人，然后以儿子的编号作为数组索引，将目标位置修改为父亲的编号。  
例如输入数据 3 1，将 3 号索引的位置改成1，代表 3 号是 1 号的儿子  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDY5NA_size_16_color_FFFFFF_t_70_pic_center 1]

private static int[] people;
    
    public static void main(String[] args){ 
    	Scanner input = new Scanner(System.in);
    	int n = input.nextInt();
    	int m = input.nextInt();
    	people = new int[n + 1];
    	//首先将自己的爹设为自己，因为读取数据前，每个人都有可能是顶级祖先
    	for(int i = 1; i <= n; i++) {  people[i] = i; }
    	//开始读取父子关系数据
    	while(m-- > 0){ 
    		int son = input.nextInt();
    		int father = input.nextInt();
    		//认爹
    		people[son] = father;
    	}
    	int a = input.nextInt();
    	int b = input.nextInt();
    	//如果a、b的顶级祖先是一个人，他俩就是一家人
    	System.out.println( getAncestor(a) == getAncestor(b) );
    }
    
    //找到 p 的顶级祖先
    private static int getAncestor(int p){ 
    	//如果我爹是自己，那么我就是顶级祖先
    	if(people[p] == p){ 
    		return p;
    	}else{ 
    		//否则问我爹，咱祖先是谁
    		return getAncestor(people[p]);
    	}
    }

# 方式二 #

归一式并查集。

如果有多组查询，方式一这种逐级上问的效率就会很低，可能会有大量的重复询问。

所以方式二做个优化，如果一个人已经知道了自己的顶级祖先，就可以让自己直接记住祖先是谁就好了，下次再问我，我直接就能给出答案。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDY5NA_size_16_color_FFFFFF_t_70_pic_center 2]

private static int getAncestor(int p){ 
    	//如果我爹是自己，那么我就是顶级祖先
    	if(people[p] == p){ 
    		return p;
    	}else{ 
    		//否则问我爹，咱祖先是谁
    		//增加回溯，我爹打听到的祖先，我也记下来
    		return people[p] = getAncestor(people[p]);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDY5NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/8594ca8f806f45928e081dc784b41c80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDY5NA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/2937d0434a17459a9cdcd405caa431bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwMDY5NA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221119/a3ce52cd20fc42d3a970f9c3fbf92164.png