上一篇中我們進(jìn)行了散列表的相關(guān)練習(xí)，在這一篇中我們要學(xué)習(xí)的是并查集。

在許多實(shí)際應(yīng)用場(chǎng)景中，我們需要對(duì)元素進(jìn)行分組，并且在這些分組中進(jìn)行查詢和修改操作。比如，在圖論中，我們需要將節(jié)點(diǎn)按照連通性進(jìn)行分組，以便進(jìn)行最小生成樹、最短路徑等算法；在計(jì)算機(jī)視覺中，我們需要將像素進(jìn)行分組，以便進(jìn)行圖像分割和對(duì)象識(shí)別等任務(wù)。而并查集正是為了解決這些問題而被提出來的一種數(shù)據(jù)結(jié)構(gòu)。

概念

并查集（Disjoint Set）是一種用于處理元素分組的數(shù)據(jù)結(jié)構(gòu)，通常用于解決一些與等價(jià)關(guān)系有關(guān)的問題，比如連通性的判斷、最小生成樹算法中的邊的合并等。

并查集中的每個(gè)元素都屬于一個(gè)集合，每個(gè)集合都有一個(gè)代表元素（也稱為根節(jié)點(diǎn)），代表元素可以用來表示整個(gè)集合。并查集支持三個(gè)基本操作：

1.MakeSet(x)：創(chuàng)建一個(gè)只包含元素 x 的新集合；
2.Find(x)：返回元素 x 所屬的集合的代表元素；
3.Union(x, y)：將元素 x 和 y 所屬的集合合并成一個(gè)新集合。

其中，F(xiàn)ind 操作可以使用路徑壓縮（Path Compression）和按秩合并（Union by Rank）優(yōu)化，以提高查詢效率。

并查集的應(yīng)用非常廣泛，比如在圖論算法中求解連通性、求解最小生成樹等問題時(shí)都會(huì)用到。

偽代碼

// 初始化并查集，每個(gè)元素單獨(dú)成集合
function MakeSet(x)
    x.parent = x
    x.rank = 0

// 查找元素所屬的集合（根節(jié)點(diǎn)），并進(jìn)行路徑壓縮
function Find(x)
    if x.parent != x
        x.parent = Find(x.parent) // 路徑壓縮：將x的父節(jié)點(diǎn)設(shè)為根節(jié)點(diǎn)
    return x.parent

// 合并兩個(gè)集合，按秩合并
function Union(x, y)
    xRoot = Find(x)
    yRoot = Find(y)
    if xRoot == yRoot
        return // 已經(jīng)在同一個(gè)集合中，無需合并
    if xRoot.rank < yRoot.rank
        xRoot.parent = yRoot
    else if xRoot.rank > yRoot.rank
        yRoot.parent = xRoot
    else
        yRoot.parent = xRoot
        xRoot.rank = xRoot.rank + 1

接下來，讓我們進(jìn)行并查集的相關(guān)練習(xí)。

選擇題

1.

選B

2.

解析：
1  -4   1  1  -3  4  4  8  -2
0   1   2  3   4  5  6  7   8


1對(duì)應(yīng)-4，則1是根節(jié)點(diǎn)且有4個(gè)子孫
又因?yàn)?span id="n5n3t3z"    class="token number">0、2、3都對(duì)應(yīng)1
所以
      1
   0 2 3 null
   
   
4對(duì)應(yīng)-3，則4是根節(jié)點(diǎn)且有3個(gè)子孫
又因?yàn)?span id="n5n3t3z"    class="token number">5、6都對(duì)應(yīng)4
所以
    4
  5  6 null
  
  
8對(duì)應(yīng)-2，則8是根節(jié)點(diǎn)且有2個(gè)子孫
又因?yàn)?span id="n5n3t3z"    class="token number">7對(duì)應(yīng)8
所以
    8
  7 null
  
將6與8所在的集合合并，且小集合合并到大集合
則
    4
  5  6 8
      7 null
所以樹根是4，對(duì)應(yīng)的編號(hào)是-5（-表示樹根，5表示4的子孫個(gè)數(shù)）

3.

可以畫出來對(duì)應(yīng)的樹
然后把小樹連到大樹上
接著從1到7遍歷
如果有父節(jié)點(diǎn)，給出父節(jié)點(diǎn)的值
如果它本身是根節(jié)點(diǎn)，則給出負(fù)號(hào)和子孫個(gè)數(shù)

填空題

編程題

7-1 朋友圈

某學(xué)校有N個(gè)學(xué)生，形成M個(gè)俱樂部。每個(gè)俱樂部里的學(xué)生有著一定相似的興趣愛好，形成一個(gè)朋友圈。一個(gè)學(xué)生可以同時(shí)屬于若干個(gè)不同的俱樂部。根據(jù)“我的朋友的朋友也是我的朋友”這個(gè)推論可以得出，如果A和B是朋友，且B和C是朋友，則A和C也是朋友。請(qǐng)編寫程序計(jì)算最大朋友圈中有多少人。

輸入格式:

輸入的第一行包含兩個(gè)正整數(shù)N（≤30000）和M（≤1000），分別代表學(xué)校的學(xué)生總數(shù)和俱樂部的個(gè)數(shù)。后面的M行每行按以下格式給出1個(gè)俱樂部的信息，其中學(xué)生從1~N編號(hào)：

第i個(gè)俱樂部的人數(shù)Mi（空格）學(xué)生1（空格）學(xué)生2 … 學(xué)生Mi

輸出格式:

輸出給出一個(gè)整數(shù)，表示在最大朋友圈中有多少人。

輸入樣例:

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

輸出樣例:

4

#include<stdio.h> 

int a[30001];  // 定義數(shù)組a，用于存儲(chǔ)并查集的父節(jié)點(diǎn)信息
int search(int b){  // 查找元素所屬的集合（根節(jié)點(diǎn)）
	if(a[b]<0){  // 如果a[b]小于0，說明b是根節(jié)點(diǎn)
		return b;  // 返回b作為集合的代表元素
	}else{
		return search(a[b]);  // 否則遞歸查找父節(jié)點(diǎn)，直到找到根節(jié)點(diǎn)
	}
}

void function(int m,int n){  // 合并兩個(gè)集合
	int x,y;
	x=search(m);  // 查找m所屬的集合（根節(jié)點(diǎn)）
	y=search(n);  // 查找n所屬的集合（根節(jié)點(diǎn)）
	if(x!=y){  // 如果m和n不在同一個(gè)集合中
		a[x]+=a[y];  // 將集合y的大小加到集合x上
		a[y]=x;  // 將集合y的父節(jié)點(diǎn)指向集合x
	}
}

int main(){
	int m,n;
	scanf("%d %d",&n,&m);  // 輸入學(xué)生數(shù)量n和關(guān)系數(shù)量m
	int i;
	for(i=0;i<=n;i++){  // 初始化并查集，每個(gè)元素單獨(dú)成集合
		a[i]=-1;  // 初始時(shí)每個(gè)元素的父節(jié)點(diǎn)為自身，且集合大小為1
	}
	int stu,j,num,num1;
	for(i=0;i<m;i++){  // 處理每組關(guān)系
		scanf("%d",&stu);  // 輸入每組關(guān)系中學(xué)生的數(shù)量
		for(j=0;j<stu;j++){  // 輸入每組關(guān)系中的學(xué)生編號(hào)
			scanf("%d",&num);
			if(j==0){
				num1=num;  // 記錄第一個(gè)學(xué)生的編號(hào)
			}else{
				function(num1,num);  // 合并這組關(guān)系中的學(xué)生
			}
		}
	}
	int min;
	min=a[1];
	for(i=2;i<n;i++){  // 找到集合中最小的負(fù)數(shù)，作為集合大小的相反數(shù)
		if(min>a[i]){
			min=a[i];
		}
	}
	printf("%d",-min);  // 輸出最少需要分成的組數(shù)
}

R7-1 笛卡爾樹

笛卡爾樹是一種特殊的二叉樹，其結(jié)點(diǎn)包含兩個(gè)關(guān)鍵字K1和K2。首先笛卡爾樹是關(guān)于K1的二叉搜索樹，即結(jié)點(diǎn)左子樹的所有K1值都比該結(jié)點(diǎn)的K1值小，右子樹則大。其次所有結(jié)點(diǎn)的K2關(guān)鍵字滿足優(yōu)先隊(duì)列（不妨設(shè)為最小堆）的順序要求，即該結(jié)點(diǎn)的K2值比其子樹中所有結(jié)點(diǎn)的K2值小。給定一棵二叉樹，請(qǐng)判斷該樹是否笛卡爾樹。

輸入格式:

輸入首先給出正整數(shù)N（≤1000），為樹中結(jié)點(diǎn)的個(gè)數(shù)。隨后N行，每行給出一個(gè)結(jié)點(diǎn)的信息，包括：結(jié)點(diǎn)的K1值、K2值、左孩子結(jié)點(diǎn)編號(hào)、右孩子結(jié)點(diǎn)編號(hào)。設(shè)結(jié)點(diǎn)從0~(N-1)順序編號(hào)。若某結(jié)點(diǎn)不存在孩子結(jié)點(diǎn)，則該位置給出?1。

輸出格式:

輸出YES如果該樹是一棵笛卡爾樹；否則輸出NO。

輸入樣例1:

6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 21 -1 4
15 22 -1 -1
5 35 -1 -1

輸出樣例1:

YES

輸入樣例2:

6
8 27 5 1
9 40 -1 -1
10 20 0 3
12 11 -1 4
15 22 -1 -1
50 35 -1 -1

輸出樣例2:

NO

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int k1;
    int k2;
    int left_c;
    int right_c;
}a[1200];  // 定義結(jié)構(gòu)體Node，表示二叉樹的每個(gè)節(jié)點(diǎn)
int root,flag=1;  // 定義變量root表示根節(jié)點(diǎn)，flag表示是否符合條件
int b[1200];  // 定義數(shù)組b，用于標(biāo)記每個(gè)節(jié)點(diǎn)是否有左右孩子
int zhongxu[1200],cnt=0;  // 定義數(shù)組zhongxu，存儲(chǔ)中序遍歷序列，cnt為元素?cái)?shù)量

void midorder(int root){  // 中序遍歷二叉樹
    if(root!=-1){  // 如果根節(jié)點(diǎn)不為空
        midorder(a[root].left_c);  // 遍歷左子樹
        zhongxu[cnt]=a[root].k1;  // 將當(dāng)前節(jié)點(diǎn)的值存入中序遍歷序列中
        cnt++;  // 記錄元素?cái)?shù)量
        midorder(a[root].right_c);  // 遍歷右子樹
    }
}

void judgeheap(int root){  // 判斷是否為堆
    int left,right;
    if(a[root].left_c!=-1){  // 如果左孩子存在
        left=a[root].left_c;
        if(a[left].k2<a[root].k2){  // 如果左孩子的值小于根節(jié)點(diǎn)的值
            flag=0;  // 不符合堆的條件
            return ;
        }
        judgeheap(left);  // 遞歸遍歷左子樹
    }
    if(a[root].right_c!=-1){  // 如果右孩子存在
        right=a[root].right_c;
        if(a[right].k2<a[root].k2){  // 如果右孩子的值小于根節(jié)點(diǎn)的值
            flag=0;  // 不符合堆的條件
            return ;
        }
        judgeheap(right);  // 遞歸遍歷右子樹
    }
}

int main()
{
    int n;
    cin>>n;  // 輸入節(jié)點(diǎn)數(shù)量n
    int i,K1,K2,Left,Right;
    memset(b,0,sizeof(b));  // 初始化數(shù)組b，全部置為0
    for(i=0;i<n;i++)  // 處理每個(gè)節(jié)點(diǎn)的信息
    {
        scanf("%d %d %d %d",&K1,&K2,&Left,&Right);  // 輸入節(jié)點(diǎn)的值、權(quán)值、左右孩子的編號(hào)
        a[i].k1=K1;  // 將節(jié)點(diǎn)的值存入結(jié)構(gòu)體
        a[i].k2=K2;  // 將節(jié)點(diǎn)的權(quán)值存入結(jié)構(gòu)體
        a[i].left_c=Left;  // 將左孩子編號(hào)存入結(jié)構(gòu)體
        a[i].right_c=Right;  // 將右孩子編號(hào)存入結(jié)構(gòu)體
        if(Left!=-1)  // 如果左孩子存在
            b[Left]=1;  // 標(biāo)記左孩子編號(hào)為1
        if(Right!=-1)  // 如果右孩子存在
            b[Right]=1;  // 標(biāo)記右孩子編號(hào)為1  
    }  
    for(i=0;i<n;i++){  // 找到根節(jié)點(diǎn)
        if(b[i]==0){  // 如果節(jié)點(diǎn)沒有左右孩子，說明其為根節(jié)點(diǎn)
            root=i;
            break;
        }
    }
    midorder(root);  // 中序遍歷二叉樹，得到中序遍歷序列
    for(i=1;i<cnt;i++){  // 判斷是否為完全二叉樹
        if(zhongxu[i]<=zhongxu[i-1]){  // 如果中序遍歷序列不是單調(diào)遞增的
            flag=0;  // 不符合完全二叉樹的條件
            break;
        }
    }
    judgeheap(root);  // 判斷是否為堆
    if(flag)  // 如果符合條件
        printf("YES\n");  // 輸出YES
    else
       printf("NO\n");  // 輸出NO
    return 0;
}

R7-2 部落

在一個(gè)社區(qū)里，每個(gè)人都有自己的小圈子，還可能同時(shí)屬于很多不同的朋友圈。我們認(rèn)為朋友的朋友都算在一個(gè)部落里，于是要請(qǐng)你統(tǒng)計(jì)一下，在一個(gè)給定社區(qū)中，到底有多少個(gè)互不相交的部落？并且檢查任意兩個(gè)人是否屬于同一個(gè)部落。

輸入格式：

輸入在第一行給出一個(gè)正整數(shù)N（≤104），是已知小圈子的個(gè)數(shù)。隨后N行，每行按下列格式給出一個(gè)小圈子里的人：

K P[1] P[2] ? P[K]

其中K是小圈子里的人數(shù)，P[i]（i=1,?,K）是小圈子里每個(gè)人的編號(hào)。這里所有人的編號(hào)從1開始連續(xù)編號(hào)，最大編號(hào)不會(huì)超過104。

之后一行給出一個(gè)非負(fù)整數(shù)Q（≤104），是查詢次數(shù)。隨后Q行，每行給出一對(duì)被查詢的人的編號(hào)。

輸出格式：

首先在一行中輸出這個(gè)社區(qū)的總?cè)藬?shù)、以及互不相交的部落的個(gè)數(shù)。隨后對(duì)每一次查詢，如果他們屬于同一個(gè)部落，則在一行中輸出Y，否則輸出N。

輸入樣例：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

輸出樣例：

10 2
Y
N

#include<iostream>
#include<set>
#include<cstdio>
using namespace std;
int pre[10010];  // 定義數(shù)組pre，用于存儲(chǔ)每個(gè)元素的祖先

int find(int x){  // 查找操作，返回x的祖先
    if(pre[x]==x) return x;
    return pre[x]=find(pre[x]);
} 

void unite(int x,int y){  // 合并操作，將x所在集合和y所在集合合并
    x=find(x);
    y=find(y);
    if(x!=y)
        pre[x]=y;
}

int main(){
    int n,x,y,m,a;
    for(int i=1;i<=10000;i++) pre[i]=i;  // 初始化每個(gè)元素的祖先為自身
    set<int>s,ss;  // 定義兩個(gè)set容器s和ss，分別用于存儲(chǔ)所有元素和合并后的元素
    cin>>n;  // 輸入集合數(shù)量n
    while(n--){  // 處理每個(gè)集合
        cin>>m;  // 輸入集合中元素?cái)?shù)量m
        cin>>x;  // 輸入第一個(gè)元素的值
        s.insert(x);  // 將第一個(gè)元素插入到集合s中
        for(int i=1;i<m;i++){  // 處理集合中的其他元素
            cin>>y;  // 輸入元素的值
            s.insert(y);  // 將元素插入到集合s中
            unite(x,y);  // 將元素x和元素y所在的集合合并
        }
    }
    set<int>::iterator it;  // 定義迭代器it，用于遍歷集合s中的元素
    for(it=s.begin();it!=s.end();it++)  // 遍歷集合s中的元素
        ss.insert(find(*it));  // 將每個(gè)元素的祖先插入到集合ss中
    printf("%d %d\n",s.size(),ss.size());  // 輸出集合s的大小和集合ss的大小
    cin>>a;  // 輸入查詢次數(shù)a
    while(a--){  // 處理每次查詢
        cin>>x>>y;  // 輸入要查詢的兩個(gè)元素
        if(find(x)==find(y))  // 如果兩個(gè)元素的祖先相同
            puts("Y");  // 輸出Y
        else
            puts("N");  // 輸出N
    }
    return 0;
}

R7-3 秀恩愛分得快

古人云：秀恩愛，分得快。

互聯(lián)網(wǎng)上每天都有大量人發(fā)布大量照片，我們通過分析這些照片，可以分析人與人之間的親密度。如果一張照片上出現(xiàn)了 K 個(gè)人，這些人兩兩間的親密度就被定義為 1/K。任意兩個(gè)人如果同時(shí)出現(xiàn)在若干張照片里，他們之間的親密度就是所有這些同框照片對(duì)應(yīng)的親密度之和。下面給定一批照片，請(qǐng)你分析一對(duì)給定的情侶，看看他們分別有沒有親密度更高的異性朋友？

輸入格式：

輸入在第一行給出 2 個(gè)正整數(shù)：N（不超過1000，為總?cè)藬?shù)——簡(jiǎn)單起見，我們把所有人從 0 到 N-1 編號(hào)。為了區(qū)分性別，我們用編號(hào)前的負(fù)號(hào)表示女性）和 M（不超過1000，為照片總數(shù)）。隨后 M 行，每行給出一張照片的信息，格式如下：

K P[1] ... P[K]

其中 K（≤ 500）是該照片中出現(xiàn)的人數(shù)，P[1] ~ P[K] 就是這些人的編號(hào)。最后一行給出一對(duì)異性情侶的編號(hào) A 和 B。同行數(shù)字以空格分隔。題目保證每個(gè)人只有一個(gè)性別，并且不會(huì)在同一張照片里出現(xiàn)多次。

輸出格式：

首先輸出 A PA，其中 PA 是與 A 最親密的異性。如果 PA 不唯一，則按他們編號(hào)的絕對(duì)值遞增輸出；然后類似地輸出 B PB。但如果 A 和 B 正是彼此親密度最高的一對(duì)，則只輸出他們的編號(hào)，無論是否還有其他人并列。

輸入樣例 1：

10 4
4 -1 2 -3 4
4 2 -3 -5 -6
3 2 4 -5
3 -6 0 2
-3 2

輸出樣例 1：

-3 2
2 -5
2 -6

輸入樣例 2：

4 4
4 -1 2 -3 0
2 0 -3
2 2 -3
2 -1 2 
-3 2

輸出樣例 2：

-3 2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define maxn 4019
int n,m,k[maxn],A,B,sexa,sexb; //人數(shù)，圖片數(shù)，每張圖片的人數(shù)數(shù)組，兩個(gè)人的編號(hào)，兩個(gè)人的性別
int fu[maxn],pic[maxn][maxn],pwa[maxn],pwb[maxn]; //人的性別數(shù)組，圖片中的人物編號(hào)數(shù)組，用于計(jì)算親密度的臨時(shí)數(shù)組
double pa[maxn],pb[maxn]; //與A、B的親密度數(shù)組
vector<int>ans1,ans2; //存儲(chǔ)親密度最高的人的編號(hào)
 
struct gg
{
    int id; //人的編號(hào)
    double v; //與A或B的親密程度
} p1[maxn],p2[maxn]; //用于排序的臨時(shí)結(jié)構(gòu)體數(shù)組
 
//讀取帶負(fù)號(hào)的字符串并轉(zhuǎn)換為整數(shù)
int read(char*str,int ans,int *fu_)
{
    if(str[0]=='-')
    {
        int len=strlen(str);
        rep(t,1,len)
        ans=ans*10+str[t]-'0';
        *fu_=-1; //標(biāo)記為負(fù)數(shù)
    }
    else
    {
        int len=strlen(str);
        rep(t,0,len)
        ans=ans*10+str[t]-'0';
        *fu_=0; //標(biāo)記為非負(fù)數(shù)
    }
    return ans;
}
 
//根據(jù)性別計(jì)算與A或B的親密度
void getpwith_(int index,int row)
{
    memset(pwa,0,sizeof(pwa)); //清空臨時(shí)數(shù)組
    int sex=index==1?sexa:sexb; //根據(jù)index確定性別
 
    rep(j,0,k[row])
    {
        int peo=pic[row][j];
        if(fu[peo]!=sex) //與A或B的性別不同的人，親密度加1
        {
            if(index)
                pwa[peo]=1;
            else
                pwb[peo]=1;
        }
    }
}
 
//比較函數(shù)，用于排序
int cmp(gg x,gg y)
{
    if(x.v!=y.v)
        return x.v>y.v;
    return x.id<y.id;
}
 
int main()
{
    scanf("%d%d",&n,&m); //讀取人數(shù)和圖片數(shù)
    rep(i,0,m)
    {
        scanf("%d",&k[i]); //讀取每張圖片中的人數(shù)
        char str[maxn];
 
        //(1)讀取pic[][]:存儲(chǔ)出現(xiàn)過的每張圖片里的具體人物編號(hào)和性別
        rep(j,0,k[i])
        {
            scanf("%s",str);
            //讀取多位數(shù)
            int fu_;
            pic[i][j]=read(str,pic[i][j],&fu_); //讀取人物編號(hào)并標(biāo)記性別
            fu[pic[i][j]]=fu_; //記錄人的性別
        }
    }
    char AA[maxn],BB[maxn];
    scanf("%s%s",AA,BB); //讀取兩個(gè)人的編號(hào)字符串
    A=read(AA,0,&sexa); //將字符串轉(zhuǎn)換為整數(shù)，并記錄性別
    B=read(BB,0,&sexb);
 
    /*當(dāng)某個(gè)人和誰的好感度都是0，這時(shí)候只輸出所有異性*/
    rep(i,0,n){
        if(fu[i]==sexa)
            pa[i]+=-1; //當(dāng)與A的親密度為0時(shí)，將其置為-1
        if(fu[i]==sexb)
            pb[i]+=-1; //當(dāng)與B的親密度為0時(shí)，將其置為-1
    }
 
    //(2)計(jì)算flaga,flagb(局部變量):標(biāo)記計(jì)算m張圖片里是否出現(xiàn)過A,B
    rep(i,0,m)
    {
        int flaga=0;
        int flagb=0;
        rep(j,0,k[i])
        {
            if(pic[i][j]==A)
                flaga=1; //標(biāo)記A在當(dāng)前圖片中出現(xiàn)過
            if(pic[i][j]==B)
                flagb=1; //標(biāo)記B在當(dāng)前圖片中出現(xiàn)過
        }
 
        if(flaga) //計(jì)算A在局部和每個(gè)人同框的次數(shù)
        {
            getpwith_(1,i); //計(jì)算與A的親密度
            rep(j,0,k[i])
            pa[pic[i][j]]+=pwa[pic[i][j]]/double(k[i]); //累加親密度
        }
        if(flagb)//計(jì)算B在局部和每個(gè)人同框的次數(shù)
        {
            getpwith_(0,i); //計(jì)算與B的親密度
            rep(j,0,k[i])
            pb[pic[i][j]]+=pwb[pic[i][j]]/double(k[i]); //累加親密度
        }
    }
 
    rep(i,0,n)
        p1[i].id=i,p1[i].v=pa[i],p2[i].id=i,p2[i].v=pb[i]; //初始化結(jié)構(gòu)體數(shù)組
 
    sort(p1,p1+n,cmp); //按親密度排序
    sort(p2,p2+n,cmp);
 
    double maxa=p1[0].v; //A的最大親密度
    rep(i,0,n)
    {
        if(p1[i].v!=maxa)
            break;
        else
            ans1.push_back(p1[i].id); //將親密度最高的人的編號(hào)存入ans1
    }
 
    double maxb=p2[0].v; //B的最大親密度
    rep(i,0,n)
    {
        if(p2[i].v!=maxb)
            break;
        else
            ans2.push_back(p2[i].id); //將親密度最高的人的編號(hào)存入ans2
    }
 
    int len1=ans1.size();
    int f1=0;
    rep(i,0,len1)
    {
        if(pa[ans1[i]]==pa[B]) //如果與B的親密度與A的親密度相同，則標(biāo)記f1
            f1=1;
    }
 
    int len2=ans2.size();
    int f2=0;
    rep(i,0,len2)
    {
        if(pb[ans2[i]]==pb[A]) //如果與A的親密度與B的親密度相同，則標(biāo)記f2
            f2=1;
    }
 
    if(f1&&f2) //如果同時(shí)滿足與A和B的親密度相同的人存在，輸出兩個(gè)人的編號(hào)
    {
        if(sexa==-1)
            cout<<'-'<<A<<" ";
        else
            cout<<A<<" ";
        if(sexb==-1)
            cout<<'-'<<B<<endl;
        else
            cout<<B<<endl;
    }
    else //否則，分別輸出與A和B親密度最高的人的編號(hào)
    {
        rep(i,0,len1)
        {
            if(sexa==-1)
                cout<<'-'<<A<<" ";
            else
                cout<<A<<" ";
            if(fu[ans1[i]]==-1)
                cout<<'-'<<ans1[i]<<endl;
            else
                cout<<ans1[i]<<endl;
        }
        rep(i,0,len2)
        {
            if(sexb==-1)
                cout<<'-'<<B<<" ";
            else
                cout<<B<<" ";
            if(fu[ans2[i]]==-1)
                cout<<'-'<<ans2[i]<<endl;
            else
                cout<<ans2[i]<<endl;
        }
 
    }
 
    return 0;
}

以上就是并查集的知識(shí)點(diǎn)及相關(guān)練習(xí)了，在下一篇文章中我們將學(xué)習(xí)圖的相關(guān)知識(shí)點(diǎn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-773236.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)入門精講 | 第十六篇】并查集知識(shí)點(diǎn)及考研408、企業(yè)面試練習(xí)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！