圖論：并查集求最小環
概念：
圖、路、環：
一個有向圖由G=(N,A)表示，其中N表示節點集，A表示邊集邊(i,j)為一有序對，i為出發節點，j為終止節點，在無向圖中(i,j)與(j,i)一致，
路是由節點及其對應的邊依次相連構成，
環是出發節點和終止節點相同的路，
如果一條路不含重復邊和重復節點，就被稱做簡單路，出發節點和終止節點相同的簡單路就被稱為簡單環，
對于有向圖而言 可以使用拓撲排序的方式找出圖中的環
引入例題：
P2661 資訊傳遞
題目描述
有 nnn 個同學（編號為 111 到 nnn ）正在玩一個資訊傳遞的游戲，在游戲里每人都有一個固定的資訊傳遞物件，其中，編號為 iii 的同學的資訊傳遞物件是編號為 TiT_iTi 的同學，
游戲開始時，每人都只知道自己的生日，之后每一輪中，所有人會同時將自己當前所知的生日資訊告訴各自的資訊傳遞物件（注意：可能有人可以從若干人那里獲取資訊， 但是每人只會把資訊告訴一個人，即自己的資訊傳遞物件），當有人從別人口中得知自 己的生日時，游戲結束，請問該游戲一共可以進行幾輪？
輸入格式
共2行，
第1行包含1個正整數 n ，表示 n 個人，
第2行包含 n 個用空格隔開的正整數 T1,T2,???,Tn，其中第 iii 個整數 Ti 表示編號為 i 的同學的資訊傳遞物件是編號為 Ti 的同學， Ti≤n 且 Ti≠i，
輸出格式
1個整數，表示游戲一共可以進行多少輪，
輸入輸出樣例
輸入 #1
5 2 4 2 3 1輸出 #1
3說明/提示
樣例1解釋
游戲的流程如圖所示，當進行完第3 輪游戲后， 4號玩家會聽到 2 號玩家告訴他自己的生日，所以答案為 3，當然，第 3輪游戲后，2號玩家、3 號玩家都能從自己的訊息來源得知自己的生日，同樣符合游戲結束的條件，
對于 30%的資料， n≤200；
對于 60%的資料， n≤2500；
對于100%的資料， n≤200000，
決議：
首先，通過題目可能想到的是暴力建立set判重，
本題難點在于，怎么看出他是一并查集的題，講真，題目的描述，一輪一輪的感覺與并查集風牛馬牛不相及，但是非要聯系的話，首先想到是：圖，那把圖畫出來：
![]](https://img.uj5u.com/2020/12/03/200576031058092.png)
畫完我們得知，要求的游戲輪數，就抽象在這個環里，簡言之就是：存在環的話，生日就可以傳到自己耳朵里，傳遞次數為環的大小，
來源題解：
anyway
把每個同學看成一個點，資訊的傳遞就是在他們之間連有向邊，游戲輪數就是求最小環，
圖論求最小環，我在里面看到了并查集，
假如說資訊由A傳遞給B，那么就連一條由A指向B的邊，同時更新A的父節點**，A到它的父節點的路徑長也就是B到它的父節點的路徑長+1，**
這樣我們就建立好了一個圖，之后資訊傳遞的所有環節都按照這些路徑，游戲結束的輪數，也就是這個圖里最小環的長度，
如果有兩個點祖先節點相同，那么就可以構成一個環，長度為兩個點到祖先節點長度之和+1，
和下面的并查集有點不一樣的，
代碼：
（簡略注釋在代碼中給出，*下方有詳細解釋）
import java.util.Scanner;
/*
* P2661 資訊傳遞 并查集求最小環
*/
public class P2661 {
static Scanner sc= new Scanner(System.in);
static int n=sc.nextInt();
static int f[]=new int[200005];//這是節點的父節點陣列
static int d[]=new int[200005];//這是到父節點的距離
static int min=n;//設定一個最小環數（初始值設為最大）
public static void main(String[] args) {
for (int i = 1; i <= n; i++) {
f[i]=i;//初始化，讓自己當自己的”嗲“；
}
for (int i = 1; i <=n ; i++) {
int to=sc.nextInt();
check(i,to);//------------------------------------*1*
}
System.out.println(min);
}
private static void check(int i, int to) {
// 經典check函式
int x=getfa(i);
int y=getfa(to);//找爹，也就是“讓boss之間談話”
if(x!=y){
f[x]=y;//讓boss會話，并認右為王
d[i]=d[to]+1;//-----------------------------------*2*
}else{
min=Math.min(min, d[i]+d[to]+1);//----------------*3*
//長度為兩個點到祖先節點長度之和+1，
}
}
private static int getfa(int x) {
//經典找爹函式
if(f[x]!=x){
int origin=f[x];
f[x]=getfa(f[x]);//小細節：不是getfa(x)是getfa(f[x]);
d[x]+=d[origin];//-------------------------------*4*
//更新路徑長（原來連在父節點上），
}
return f[x];
}
}
難點&精彩點：
-
首先就是并查集的知識：建議先學幾個并查集的例子在做這個題，否則不懂，強推《啊哈！演算法》p200頁的知識，記住“擒賊先擒王的口訣”和“以左為王”的口訣
-
*1*這里我認為理解起來有難度，（呵呵，也許是我太笨，反正就這個回圈，我受題面“輪數”影響，想了好久才想出來）這里其實和題目的輪數無關，以后也不要記輪數了，總之就是要把這幾個點一個個輸入，邊輸入邊判斷已有的點集合，是否存在環，以及是否存在最小值，
-
*2*這里的d[i]=d[to]+1;要點有二，一是方括號里必須是判斷值，而不是其父值，也就是說”找祖宗“只是為了判斷是否在一點集內，而對父節點的距離陣列進行記錄時是對i,to,操作的，而加一操作見下圖：
-
*3*,這個地方，，怎么說，代碼作者很強，應該是分析出的規律：長度為兩個點到祖先節點長度之和+1，
-
*4*這地方，的確很難想，這個地方和路徑壓縮有關，很巧妙，我試了試，只能把他放在遞回后側回溯的程序中，然后相當于“拾級而上，不斷累加”太難想了對我···哈哈感覺遇到了瓶頸，（菜雞的瓶頸未免也太低啦哈哈）
小結：
很好的考察了并查集，遞回，圖論的部分知識，尤其是在兩個經典并查集函式中，其中關于路徑的記錄很考察人的水平，
，這個地方和路徑壓縮有關，很巧妙，我試了試，只能把他放在遞回后側回溯的程序中，然后相當于“拾級而上，不斷累加”太難想了對我···哈哈感覺遇到了瓶頸，（菜雞的瓶頸未免也太低啦哈哈）
小結：
很好的考察了并查集，遞回，圖論的部分知識，尤其是在兩個經典并查集函式中，其中關于路徑的記錄很考察人的水平，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/229318.html
標籤：其他
上一篇：免費實用的錄屏工具！支持全屏、特定視窗、選定區域錄制，支持添加水印、嵌入攝像頭！
下一篇：Unity實作BStar尋路