由于時(shí)間太久忘記出處了，不好意思...找到后補(bǔ)上.
并查集 (Union-Find Sets)
并查集： (union-find sets)是一種簡(jiǎn)單的用
途廣泛的集合. 并查集是若干個(gè)不相交集合，能夠?qū)崿F(xiàn)較快的合并和判斷元素所在集合的操作，應(yīng)用很
多。一般采取樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)并查集，并利用一個(gè)rank數(shù)組來(lái)存儲(chǔ)集合的深度下界，在查找操作時(shí)進(jìn)
行路徑壓縮使后續(xù)的查找操作加速。這樣優(yōu)化實(shí)現(xiàn)的并查集，空間復(fù)雜度為O(N)，建立一個(gè)集合的時(shí)
間復(fù)雜度為O(1)，N次合并M查找的時(shí)間復(fù)雜度為O(M Alpha(N))，這里Alpha是Ackerman函數(shù)的某個(gè)反函數(shù)，在很
大的范圍內(nèi)（人類目前觀測(cè)到的宇宙范圍估算有10的80次
方個(gè)原子，這小于前面所說(shuō)的范圍）這個(gè)函數(shù)的值可以看成是不大于4的，所以并查集的操作可以看作是
線性的。它支持以下三中種操作:
－Union (Root1, Root2) //并
操作；把子集合Root2并入集合Root1中.要求：Root1和 Root2互不相交,否則不執(zhí)行操作.
－Find (x) //搜索操作；搜索單元素x所在的集
合,并返回該集合的名字.
－UFSets
(s) //構(gòu)造函數(shù)。將并查集中s個(gè)元素初始化為s個(gè)只有一個(gè)單元素的子集合.
－對(duì)于并查集來(lái)說(shuō)，每個(gè)集合用一棵樹(shù)表示。
－集合中每個(gè)元素的元素名分別存放在樹(shù)的結(jié)
點(diǎn)中，此外，樹(shù)的每一個(gè)結(jié)點(diǎn)還有一個(gè)指向其雙親結(jié)點(diǎn)的指針。
－設(shè) S1= {0, 6, 7, 8 }，S2= { 1, 4, 9 }，S3= { 2, 3, 5 }
－為簡(jiǎn)化討論，忽略實(shí)際的集合名，僅用表示集合的樹(shù)的根來(lái)標(biāo)識(shí)
集合。
－為此，采用樹(shù)的雙親表示作為集合存儲(chǔ)表示。集合元素的編號(hào)從0到 n-1。其中 n 是最大元素個(gè)數(shù)。在雙親表示中，第 i 個(gè)數(shù)組元
素代表包含集合元素 i 的樹(shù)結(jié)點(diǎn)。根結(jié)點(diǎn)的雙親為-1，
表示集合中的元素個(gè)數(shù)。為了區(qū)別雙親指針信息( ≥ 0 )，集合元素個(gè)數(shù)信息用負(fù)數(shù)表示。
|
下標(biāo) 
parent
|
|
集合 S1,
S2 和 S3 的雙親表示 : 
S1
∪ S2 的可能的表示方法
const int DefaultSize = 10;
class
UFSets { //并查集的類定義
private:
int *parent;
int size;
public:
UFSets ( int s =
DefaultSize );
~UFSets ( ) { delete [ ] parent; }
UFSets & operator = ( UFSets const & Value
);//集合
賦值
void
Union ( int Root1, int Root2 );
int Find ( int x );
void
UnionByHeight ( int Root1, int Root2 ); };
UFSets::UFSets ( int s ) { //構(gòu)造函數(shù)
size = s;
parent = new int [size+1];
for ( int i = 0; i <=
size; i++ ) parent[i] = -1;
}
unsigned int UFSets::Find ( int x ) { //搜索操作
if ( parent[x] <= 0 )
return x;
else return Find ( parent[x] );
}
void UFSets::Union ( int Root1, int Root2 ) { //并
parent[Root2] = Root1; //Root2指向Root1
}
Find和Union操作性能不好。假設(shè)最初 n 個(gè)元素構(gòu)成 n 棵樹(shù)組成的森林，parent[i] = -1。
做處理Union(0, 1), Union(1, 2), …, Union(n-2, n-1)后，
將產(chǎn)生如圖所示的退化的樹(shù)。
執(zhí)行一次Union操作所需時(shí)間是O(1)，n-1次Union操作所需時(shí)間是O(n)。若再執(zhí)行Find(0), Find(1), …,
Find(n-1), 若被
搜索的元素為i，完成Find(i)操
作需要時(shí)間為O(i)，完成 n 次搜索需
要的總時(shí)間將達(dá)到
Union操作的加權(quán)規(guī)則
為避免產(chǎn)生退化的樹(shù)，改進(jìn)方法是先判斷兩集合中元素的個(gè)數(shù)，如果以 i 為根的樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)少于
以 j 為根的樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)，即parent[i]
> parent[j]，則讓 j 成為 i 的雙親，否則，讓i成為j的雙親。此即Union的加權(quán)規(guī)則。 
parent[0](== -4) < parent[4]
(== -3)
void
UFSets::WeightedUnion(int Root1, int Root2) {
//按Union的加權(quán)規(guī)則改進(jìn)的算法
int temp = parent[Root1] +
parent[Root2];
if ( parent[Root2] < parent[Root1] ) {
parent[Root1] = Root2; //Root2中結(jié)點(diǎn)數(shù)多
parent[Root2] = temp; //Root1指向Root2
}
else {
parent[Root2] =
Root1; //Root1中結(jié)點(diǎn)數(shù)多
parent[Root1] = temp; //Root2指向Root1
}
}
使用加權(quán)規(guī)則得到的樹(shù)
下面是幾到用并查集可以方便解決的問(wèn)題:
題目： 親戚(Relations)
或許你并不知道，你的某個(gè)朋友是你的親戚。他可能是你的曾祖父
的外公的女婿的外甥的表姐的孫子。如果能得到完整的家譜，判斷兩個(gè)人是否親戚應(yīng)該是可行的，但如果兩個(gè)人的最近公共祖先與他們相隔好幾代，使得家譜十分龐
大，那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及.在這種情況下，最好的幫手就是計(jì)算機(jī)。
為了將問(wèn)題簡(jiǎn)化，你將得到一些親戚關(guān)系的信息，如同Marry和Tom是親戚，Tom和B en是親戚，等等。從這些信息中，你可以推出Marry和Ben是親戚。請(qǐng)寫一個(gè)程序，對(duì)于我們的關(guān)
心的親戚關(guān)系的提問(wèn)，以最快的速度給出答案。
參考輸入輸出格式 輸入由兩部分組成。
第一部分以N，M開(kāi)始。N為問(wèn)題涉及的人的個(gè)數(shù)(1 ≤ N ≤
20000)。這些人的編號(hào)為1,2,3,…,N。下面有M行(1
≤ M ≤ 1000000)，
每行有兩個(gè)數(shù)ai, bi，表示已知ai和bi是親戚.
第二部分以Q開(kāi)
始。以下Q行有Q個(gè)詢問(wèn)(1 ≤ Q ≤
1 000 000)，每行為ci, di，表示詢問(wèn)ci和di是否為親戚。
對(duì)于每個(gè)詢問(wèn)ci,
di，若ci和di為親戚，
則輸出Yes，否則輸出No。
樣例輸入與輸出
輸入relation.in
10
7
2
4
5
7
1
3
8
9
1
2
5
6
2
3
3
3
4
7
10
8
9
輸出relation.out
Yes
No
Yes
如果這道題目不用并查集，而只
用鏈表或數(shù)組來(lái)存儲(chǔ)集合，那么效率很低，肯定超時(shí)。
例程:
#include<iostream>
using namespace
std;
int N,M,Q;
int
pre[20000],rank[20000];
void makeset(int x)
{
pre[x]=-1;
rank[x]=0;
}
int find(int x)
{
int r=x;
while(pre[r]!=-1)
r=pre[r];
while(x!=r)
{
int q=pre[x];
pre[x]=r;
x=q;
}
return
r;
}
void unionone(int
a,int b)
{
int t1=find(a);
int t2=find(b);
if(rank[t1]>rank[t2])
pre[t2]=t1;
else
pre[t1]=t2;
if(rank[t1]==rank[t2])
rank[t2]++;
}
int main()
{
int
i,a,b,c,d;
while(cin>>N>>M)
{
for(i=1;i<=N;i++)
makeset(i);
for(i=1;i<=M;i++)
{
cin>>a>>b;
if(find(a)!=find(b))
unionone(a,b);
}
cin>>Q;
for(i=1;i<=Q;i++)
{
cin>>c>>d;
if(find(c)==find(d))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return
0;
}
ZJU1789The Suspects
【問(wèn)題描述】
Severe acute
respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology,
was recognized as a global threat in mid-March 2003. To minimize
transmission to others, the best strategy is to separate the suspects
from others.
In the
Not-Spreading-Your-Sickness University (NSYSU), there are many student
groups. Students in the same group intercommunicate with each other
frequently, and a student may join several groups. To prevent the
possible transmissions of SARS, the NSYSU collects the member lists of
all student groups, and makes the following rule in their standard
operation procedure (SOP).
Once a member in a group
is a suspect, all members in the group are suspects.
However, they find that
it is not easy to identify all the suspects when a student is recognized
as a suspect. Your job is to write a program which finds all the
suspects.
Input
The input contains
several cases. Each test case begins with two integers n and m in a
line, where n is the number of students, and m is the number of groups.
You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every
student is numbered by a unique integer between 0 and n-1, and initially
student 0 is recognized as a suspect in all the cases. This line is
followed by m member lists of the groups, one line per group. Each line
begins with an integer k by itself representing the number of members in
the group. Following the number of members, there are k integers
representing the students in this group. All the integers in a line are
separated by at least one space.
A case with n = 0 and m =
0 indicates the end of the input, and need not be processed.
Output
For each case, output the
number of suspects in one line.
Sample Input
100 4
2 1 2
5 10 13
11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
【算法分析】
這道題的意思很簡(jiǎn)單,n個(gè)人編號(hào),從0到n-1,這n個(gè)人分成m個(gè)集合(1個(gè)人可以參加不同的集合),求的就是最后所有和0號(hào)有關(guān)系的集合的
人數(shù).
如果這道題目不用并查集，而只用鏈表或數(shù)組來(lái)存儲(chǔ)集合，那么效率
很低，肯定超時(shí).我們?cè)陬}目給出的每個(gè)集合的人員編號(hào)時(shí),進(jìn)行并查
操作,不過(guò)在進(jìn)行合并操作時(shí),合并的是兩個(gè)集合的元素個(gè)數(shù).最后
0號(hào)元素所在的集合數(shù)目就是所求.
例程 :
#include<iostream>
#include<cstdio>
using namespace
std;
const int
size=30000;
int
pre[size],num[size];
int n,m,k;
void makeset(int x)
{
pre[x]=-1;
num[x]=1;
}
int find(int x)//非遞歸壓縮路徑
{
int r=x;
while(pre[r]!=-1)
r=pre[r];
while(x!=r)
{
int q=pre[x];
pre[x]=r;
x=q;
}
return
r;
}
int unionone(int
a,int b)
{
int
t1,t2;
t1=find(a);
t2=find(b);
if(t1==t2)
return 0;
if(num[t2]<=num[t1])
{
pre[t2]=t1;
num[t1]+=num[t2];
}
else
{
pre[t1]=t2;
num[t2]+=num[t1];
}
return
0;
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j,a,b;
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
break;
for(i=0;i<n;i++)
makeset(i);
for(i=0;i<m;i++)
{
//cin>>k;
scanf("%d",&k);
if(k==0) continue;
//cin>>a;
scanf("%d",&a);
a=find(a);
for(j=1;j<k;j++)
{
//cin>>b;
scanf("%d",&b);
b=find(b);
unionone(a,b);
}
}
printf("%d\n",num[find(0)]);
}
return 0;
}
銀河英雄傳說(shuō)
【問(wèn)題描述】
公元五八○一年，地球居民遷移至金牛座α第二行星，在那里發(fā)表銀河聯(lián)邦創(chuàng)立宣言，同年改元為宇宙歷元年，
并開(kāi)始向銀河系深處拓展。
宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域 爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)
派宇宙艦隊(duì)司令萊因哈特 率領(lǐng)十萬(wàn)余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利 組織
麾下三萬(wàn)艘戰(zhàn)艦迎敵。
楊威利擅長(zhǎng)排兵布陣，巧妙運(yùn)用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場(chǎng)劃分成30000列，每列依次編號(hào)為1, 2,
…, 30000。
之后，他把自己的戰(zhàn)艦也依次編號(hào)為1, 2, …, 30000，讓第i號(hào)戰(zhàn)艦處于第i列(i =
1, 2, …, 30000)，形成“一字長(zhǎng)蛇陣”，誘敵深入。這是初始陣形。當(dāng)進(jìn)犯之?dāng)车竭_(dá)時(shí)，楊威利會(huì)多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實(shí)施密集攻擊。合
并指令為M i j，含義為讓第i號(hào)戰(zhàn)艦所在的整個(gè)戰(zhàn)艦隊(duì)列，作為一個(gè)整體（頭在前尾在后）接至第j號(hào)戰(zhàn)艦所在的戰(zhàn)艦隊(duì)列的尾部。顯然戰(zhàn)艦隊(duì)列是由處于同一列的一
個(gè)或多個(gè)戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會(huì)使隊(duì)列增大。
然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動(dòng)。在交戰(zhàn)中，他可以通過(guò)龐大的情報(bào)網(wǎng)絡(luò)隨時(shí)監(jiān)聽(tīng)楊威利的艦隊(duì)調(diào)動(dòng)指
令。
在楊威利發(fā)布指令調(diào)動(dòng)艦隊(duì)的同時(shí)，萊因哈特為了及時(shí)了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會(huì)發(fā)出一些詢問(wèn)指令：C i j。該指令意思是，詢問(wèn)電腦，
楊威利的第 i 號(hào)戰(zhàn)艦與第 j 號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有
多少戰(zhàn)艦。
作為一個(gè)資深的高級(jí)程序設(shè)計(jì)員，你被要求編寫程序分析楊威利的指令，以及回答萊因哈特的詢問(wèn)。
最終的決戰(zhàn)已經(jīng)展開(kāi)，銀河的歷史又翻過(guò)了一頁(yè)……
【輸入文件】
輸入文件galaxy.in的第一行有一個(gè)整數(shù)T（1<=T<=500,000），表示總共有T條指令。
以下有T行，每行有一條指令。指令有兩種格式：
1.
M i j ：i和j是兩個(gè)整數(shù)（1<=i
, j<=30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特竊聽(tīng)到的楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，并且保證第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦不在同一列。
2.
C i j ：i和j是兩個(gè)整數(shù)（1<=i
, j<=30000），表示指令涉及的戰(zhàn)艦編號(hào)。該指令是萊因哈特發(fā)布的詢問(wèn)指令。
【輸出文件】
輸出文件為galaxy.out。你的程序應(yīng)當(dāng)依次對(duì)輸入的每一條指令進(jìn)行分析和處理：
如果是楊威利發(fā)布的艦隊(duì)調(diào)動(dòng)指令，則表示艦隊(duì)排列發(fā)生了變化，
你的程序要注意到這一點(diǎn)，但是不要輸出任何信息；
如果是萊因哈特發(fā)布的詢問(wèn)指令，你的程序要輸出一行，僅包含
一個(gè)整數(shù)，表示在同一列上，第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦之間布置的戰(zhàn)艦數(shù)目。如果第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前不在同一列上，則輸出-1。
【樣例輸入】
4
M 2 3
C 1 2
M 2 4
C 4 2
【樣例輸出】
-1
1
【樣例說(shuō)明】
戰(zhàn)艦位置圖：表格中阿拉伯?dāng)?shù)字表示戰(zhàn)艦編號(hào)
|
|
第
一列
|
第
二列
|
第
三列
|
第
四列
|
……
|
|
初
始時(shí)
|
1
|
2
|
3
|
4
|
……
|
|
M 2 3
|
1
|
|
3
2
|
4
|
……
|
|
C 1 2
|
1號(hào)戰(zhàn)艦與2號(hào)戰(zhàn)艦不在同一列，因此輸出-1
|
|
M 2 4
|
1
|
|
|
4
3
2
|
……
|
|
C 4 2
|
4號(hào)戰(zhàn)艦與2號(hào)戰(zhàn)艦之間僅布置了一艘戰(zhàn)艦，編號(hào)為3，輸出1
|
【算法分析】
同一列的戰(zhàn)艦組成一個(gè)并查集,在集合中,我們以當(dāng)前列的第一艘戰(zhàn)艦作為集合的代表元.并查集的數(shù)據(jù)類型采用樹(shù)型,樹(shù)的根結(jié)點(diǎn)即為集合的代表元.為了查詢的效率達(dá)到最優(yōu),我們進(jìn)行了路徑壓縮的優(yōu)化:首先找到樹(shù)根,然后將路徑上所有結(jié)點(diǎn)的父結(jié)點(diǎn)改為根,使得樹(shù)的深度為1.
問(wèn)題是,題目不僅要求判別兩個(gè)結(jié)點(diǎn)是否在同一個(gè)集合(即兩艘戰(zhàn)艦是否在同一列),而且還要求計(jì)算結(jié)點(diǎn)在有序集合的位置(即每一艘戰(zhàn)艦相隔列的第一艘戰(zhàn)艦幾個(gè)位置), 我們?cè)黾恿艘粋€(gè)數(shù)組 behind[x], 記錄戰(zhàn)艦 x 在例中的相對(duì)位置 .
查找一個(gè)元素x所在集合的代表元時(shí)，先從x沿著父親節(jié)點(diǎn)找到這個(gè)集合的代表元root，然后再?gòu)?font face="Times New Roman">x開(kāi)始一次到root的遍歷，累計(jì)其間經(jīng)過(guò)的每一個(gè)子結(jié)點(diǎn)的behind值,其和即為behind[i].,如下圖所示:
按照題意,合并指令Mxy,含義是讓戰(zhàn)艦x 所在的整個(gè)戰(zhàn)艦隊(duì)列,作為一個(gè)整體(頭在前,尾在后)接至戰(zhàn)艦y所在的戰(zhàn)艦隊(duì)列的尾部,顯然兩個(gè)隊(duì)列合并成同一列后,其集合代表元為結(jié)點(diǎn)y所在的樹(shù)的根結(jié)點(diǎn)fy,x所在的樹(shù)的根結(jié)點(diǎn)fx,合并后,fx的相對(duì)位置為合并前y所在集合的結(jié)點(diǎn)數(shù), behind[fx]=num[fy],新集合的結(jié)點(diǎn)數(shù)為原來(lái)
兩個(gè)集合結(jié)點(diǎn)數(shù)的和 num[fy]+=num[fx]. 則如果戰(zhàn)艦x和戰(zhàn)艦y在同一列,則他們相隔
|behind[x]-behind[y]|-1艘戰(zhàn)艦.如
下圖:
例程 :
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace
std;
const int
size=30001;
int
pre[size],num[size],behind[size];//behind[x]戰(zhàn)艦x在列中的相對(duì)位置
int n,m,k;
void makeset(int x)
{
pre[x]=-1;
num[x]=1;
}
int find(int x)//查找結(jié)點(diǎn)x所在樹(shù)的根結(jié)點(diǎn),并對(duì)該樹(shù)進(jìn)行路徑壓縮
{
int r=x;
int j;
while(pre[r]!=-1)//找出結(jié)點(diǎn)x所在樹(shù)的根結(jié)點(diǎn)r
r=pre[r];
while(x!=r)
{
int
q=pre[x];//路徑壓縮
pre[x]=r;
j=q;
do{//迭代求出路徑上每一個(gè)子結(jié)點(diǎn)相對(duì)于r的相對(duì)位置
behind[x]+=behind[j];
j=pre[j];
}while (j!=-1);
x=q;
}
return
r;
}
void MoveShip(int
a,int b)
{
int
t1,t2;
t1=find(a);//計(jì)算a所在樹(shù)的根結(jié)點(diǎn)t1
t2=find(b);//計(jì)算b所在樹(shù)的根結(jié)點(diǎn)t2
pre[t1]=t2;//將t1的父結(jié)點(diǎn)設(shè)為t2
behind[t1]=num[t2];
//計(jì)算t1的相對(duì)位置為num[t2]
num[t2]+=num[t1];
//計(jì)算新集合的結(jié)點(diǎn)數(shù)
}
void CheckShip(int
x,int y)
{
int f1,f2;
f1=find(x);
f2=find(y);
if(f1!=f2)
cout<<-1<<endl;
else
cout<<abs(behind[x]-behind[y])-1<<endl;
}
int main()
{
freopen("galaxy.in","r",stdin);
freopen("out.txt","w",stdout);
int n,x,y;
char ch;
while(cin>>n)
{
for(int i=1;i<size;i++)
{
makeset(i);
}
memset(behind,0,sizeof(behind));
while(n--)
{
cin>>ch>>x>>y;
if(ch=='M')
MoveShip(x,y);
//處理合并指令
else if(ch=='C')
CheckShip(x,y); //處理詢問(wèn)指令
}
}
return
0;
}