4
, , . n 0 (2 k), k- ( ). . , m- . d, m,
O (d (n + m)). , , n, m = O (n) .
, . £ - , S, | S |= m. £ S, (,,...,) (,,...,) 1 2 p 1 2 q a a a £ b b b, :
1) j, j j a < b i < j i i a = b;
2) p £ q i i a = b 1£ i £ p.
, . m ( ), t (n - t +1) , £, [2].
-.
.
3.4. . , , , N. , . ... , . , .
. , , :
t:=p; WHILE t<>id[t] DO t:=id[t];
, :
t:=p; WHILE t<>id[t] DO BEGIN id[t]:= id[id[t]]; t:=id[t] END;
, , , : (i0i1i2i3i4i5i6i7i8i9...)
|
|
|
:
(i0i2i4i6i8...)
(i1i2i4i6i8...)
(i3i4i6i8...)
...
4
, , . // id ,
// sz .
FOR i:=0 TO N-1 DO BEGIN id[i]:=i; sz[i]:=1 END;
// :
WHILE NOT EOF(input) DO BEGIN READLN(p,q);
t:=p;WHILE t<>id[t] DO BEGIN id[t]:=id[id[t]];t:=id[t] END;
j:=q;WHILE j<>id[j] DO BEGIN id[j]:=id[id[j]];j:=id[j] END;
IF t<>j THEN {p,q } BEGIN WRITELN(p,q);
// :
IF sz[t]<sz[j] THEN // t j
// union(j,t): j:=jÈt: j t
BEGIN id[t]:=j; sz[j]:=sz[j]+sz[t] END
ELSE // j t
// union(t,j): t:=tÈj: t j
8 , , ...
BEGIN id[j]:=t; sz[t]:=sz[t]+sz[j] END
END
END
. . , , , ,
:
F(0)=1, F(i)=2F(i-1) i>0. F (- ).
G(n), F k, F(k)≥n. G (- ).
( ) M C*M*G(M) C 9.
. :
, . .
, . .
, , ...
( ) ( ) , .
. .
.
( ) . , , n- n , n , n. T(n) , , n, T(n). , . 10
|
|
|
T(n) , . .
. T(n) , n. T(n) n T(n) .
. , , .
, , , . , - : , .
, , , 11.
T(n) n. T(n) - , T(n). ,
.
. (amortized analysis) , , . , , ,
, . , () .
