: , .
, , , . , ᒺ . .
(MakeSet) , . , , , .
(FindSet). , , .
ᒺ (Union). , , ; . .
, , . - , .
3.1. ConnectedComponents ( ), , , , ; SameComponent .
.
ConnectedComponents
1 for ()
2 MakeSet(w)
3 end for
4 for ()
5 if
6 then Union(v,w)
7 end if
8 end for
SameComponent
1 if
2 then return true
3 else return false
4 end if
ConnectedComponents (. 3.1) . ᒺ , . , .
3.1, , : , , . , (. 3.1,).
, , . , , , ( 1 ). . , , , (. 3.2).
|
|
a)
, | , | |||||||||
)
3.1
ᒺ (Union(x,y)) , , . , , . , . .
3.2
, , , , . MakeSet(xi) , Union(x1,x2), Union(x2,x3), ,
Union(xn-1,xn). Union(x,x+1) ,
.
, - ; - , , , ,
,
.
Union . Union , . . , ᒺ , , .
, , ᒺ .
3.2. , . ᒺ , . Union :
Union(,)
1 n1=length(A) ʳ
2 n2=length(B) ʳ
3 n=max(n1,n2)
4 if n1>n2
5 then C=A
6 D=B
7 else C=B
8 D=A
9 end if
10 k=1
11 for i=n+1 to n1+n2
12 C(i)=D(k)
13 k=k+1
14 end for