現(xiàn)在有10個(gè)強(qiáng)盜。
1號(hào)強(qiáng)盜與2號(hào)強(qiáng)盜是同伙。
3號(hào)強(qiáng)盜與4號(hào)強(qiáng)盜是同伙。
5號(hào)強(qiáng)盜與2號(hào)強(qiáng)盜是同伙。
4號(hào)強(qiáng)盜與6號(hào)強(qiáng)盜是同伙。
2號(hào)強(qiáng)盜與6號(hào)強(qiáng)盜是同伙。
8號(hào)強(qiáng)盜與7號(hào)強(qiáng)盜是同伙。
9號(hào)強(qiáng)盜與7號(hào)強(qiáng)盜是同伙。
1號(hào)強(qiáng)盜與6號(hào)強(qiáng)盜是同伙。
2號(hào)強(qiáng)盜與4號(hào)強(qiáng)盜是同伙。
另外，強(qiáng)盜同伙的同伙也是同伙。你能幫助警方查出有多少個(gè)獨(dú)立的犯罪團(tuán)伙嗎？

Input：
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
第一行n m，n表示強(qiáng)盜的人數(shù)，m表示警方搜集到的m條線索。接下來的m行每一行有兩個(gè)數(shù) a b。表示強(qiáng)盜a和強(qiáng)盜b是同伙。

Output:
3

并查集實(shí)際上是通過一個(gè)一維數(shù)組來實(shí)現(xiàn)，其本質(zhì)是維護(hù)一個(gè)森林。起初，森林的每個(gè)點(diǎn)都是孤立的，這里可以將點(diǎn)理解為只有自身一個(gè)結(jié)點(diǎn)的樹，通過查找與合并，逐漸將這些樹合并為一顆大樹。其實(shí)合并的過程就是子節(jié)點(diǎn)并到父結(jié)點(diǎn)上的過程。 在每次判斷兩個(gè)結(jié)點(diǎn)是否已經(jīng)在同一顆樹中的時(shí)候，也要注意必須求其根源，必須一直往上找到其祖先結(jié)點(diǎn)（樹的根節(jié)點(diǎn)）。

解題思路：
main() {
??1.初始化數(shù)組init()
??2.輸入“關(guān)系”，每次都合并merge()
??3.有幾個(gè)f[i] = i就有幾個(gè)獨(dú)立的樹
}
init() {
??f[i] = i
}
merge() {
??1.獲取兩個(gè)點(diǎn)的祖先結(jié)點(diǎn)
??2.如果相等，則遵循“靠左原則”
}
getf() {
??1.如果f[i] = i，說明正是祖先，直接返回
??2.否則f[v] = getf( f[v] )，壓縮路徑，返回
}

import java.util.Scanner;public class Main3 {static int[] f = new int[1000];static int n, m;static int sum = 0;static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();m = input.nextInt();init();for (int i = 1; i <= m; i++) {int x = input.nextInt();int y = input.nextInt();merge(x, y);}/*** f[i]=i,說明這個(gè)結(jié)點(diǎn)的層級(jí)最高* 有多少個(gè)高層級(jí)就有幾個(gè)獨(dú)立的樹* */for (int i = 1; i <= n; i++) {if (f[i] == i) {sum++;}}System.out.println(sum);}/*** 初始化函數(shù)* 數(shù)組里面存自己的下標(biāo)* */private static void init() {for (int i = 1; i <= n; i++) {f[i] = i;}}/*** 查找父結(jié)點(diǎn)的遞歸函數(shù)* */private static int getf(int v) {if (f[v] == v) {return v;} else {/*** 壓縮路徑，每次函數(shù)返回時(shí)，將該位置的編號(hào)轉(zhuǎn)成祖宗編號(hào)* */f[v] = getf(f[v]);return f[v];}}/*** 合并兩個(gè)子集和* */private static void merge(int v, int u) {int t1 = getf(v);int t2 = getf(u);/*** 判斷祖先是否相同* */if (t1 != t2) {/*** 靠左原則* */f[t2] = t1;}} }

總結(jié)

以上是生活随笔為你收集整理的堆的应用--并查集解决“擒贼先擒王”问题（JAVA）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。