function [nc] = ncutf(g) 1 p" t' |0 d$ F. n%求割点的算法 g为邻接矩阵 nc为割点的集合 / E T. G m: H. n: f# fn=size(g,1);! L& `& { V% s/ t+ ?3 c) |
if n>=3; m9 [) A7 b4 ]) Z- }5 P; d2 x- Q
a=sum(g); 7 |- g; t; z4 l/ b1 H b=sum(a==2); 1 B" Q5 _7 C! K! D( L# Z& q if b==n & k% x3 g; k2 T fprintf('本图为圈,无割点。n') ' m. j& n! {/ T1 [: d4 D8 h nc=0; ! T) a$ s+ k* G' E end 8 s4 r( z$ Y& g$ N; R% Celse; O& j9 x: P9 E$ Q
[w,k]=dfs3(g);5 v J ^* P1 A' [5 h& X
%nc=[]; + B0 M0 d* \; A7 Y! G6 \; _; v nc=isncf(w,k);- T9 L# ~; Z5 M7 A& q" d
n=size(g,1); 8 j% \# U. l, a+ } m* F9 L$ e for i=1:n/ d& |! e& v0 F
for j=1:n . A* c$ @* |; C) v! Y$ x, K: W. { if w(i,j)>1 7 a0 O; e8 P7 H if k(i)>k(j) 8 z, \! F8 X- y1 R" _ g(i,j)=2;; l$ W( u6 ?. E% }2 z! x0 @
else 3 ^8 y9 E) p* H2 K4 Z8 k/ ^ g(i,j)=3;4 v& u" X: F7 R, ~0 @0 |) z
end i! F* i. }8 U/ ~1 G: y' h- d
end 4 g: D2 ~; d+ G' N" g end * L( O- c) Y5 Y5 q+ D+ s; A end7 _7 W6 D8 ~% p3 s1 K0 u4 u. t' B# m2 q
2 t' W$ z: V g) u' n' O for i=1:n ! D/ S2 d% h) R; s f1=find(g(i,==2); 3 ?9 s: E9 v/ _# b f2=find(g(i,==3); . h. Y. W. t8 h: i. f* `$ T1 a* i" l f=union(f1,f2);8 M% t9 f# G, k9 q& t
l(i)=min([k(f) k(i)]);& ~6 {9 o- \4 r6 B2 ^+ q
end& N. D9 N$ j/ ^0 R
5 T; o5 k, J. [0 t) |4 p7 }7 N for i=1:n6 T* ~' V$ b( f: e' Y9 A O
for j=1:n, ~; d6 }2 w: Y# { k: B" [
if g(i,j)==3 & k(i)>1&l(j)>=k(i)& M/ x0 K% X9 d7 e" k4 M r
nc=union(i,nc);$ y- n% e& o% g! V
end # M4 N2 u% @$ n% ` end& N' T) l- n5 j
end9 ^4 K% W% p! t' m P" p, i
end ; m# Q* R3 V u% R7 aend4 q* `3 B5 A! o: A D9 K* |& ~+ t/ N
: |2 Q' W- H: ?0 E" g0 V
2 n" `9 G' N- x _
function nc=isncf(w,k)( u$ L# a2 r. d- L- ?- S! P
nc=[]; # v9 W) J/ F. S5 G4 Q5 S5 C5 P. S t=zeros(size(w)); ' A3 [* ~6 U! n- y5 T8 U n=size(w,1);% ~: p9 i7 v5 W$ }
a=find(w~=0); 9 T s- t4 z. E for i=1:length(a). i5 g8 ^0 p, \! w+ t2 X
d(i)=w(a(i));2 @2 C( }3 Y3 Q. C/ P* ?4 @
if a(i)/n>floor(a(i)/n) 2 v! A4 L' h" R t(i)=floor(a(i)/n)+1;% L/ w, K& t0 ]8 A+ D" c
else6 z6 T" L+ N- `" f4 B" t
t(i)=floor(a(i)/n); 1 ~6 y& a( ^( m3 t( V end 7 V; b! I% d# C: c t1(i)=mod(a(i),n);( P, O1 ^8 Y( L$ s
if t1(i)==0 4 I" F# B5 G6 {# U t1(i)=n;, E) C3 S+ M+ q" F: ~
end, B) n' ?: L' ^5 V
end/ T8 Q4 o9 F$ u1 B5 R- H
[b,c]=sort(d); h) h X' u. {. L( c( _
p=[1];pc=0;# R B5 T. H: J1 q5 t. c
for i=1:length(a)8 _5 O/ h. [4 q/ b! Q6 v' p9 g2 C, J
if k(t1(c(i)))<k(t(c(i)))0 g3 w9 c# y* Y# D& H8 g3 c
p=union(p,t(c(i))); ! i7 v1 i v/ u# T6 [" V. _( o7 x t(t1(c(i)),t(c(i)))=3; " q* N, Y. c, a' D! t: F end9 T! S1 E- Z B$ K! E- O( U2 F
if pc==0 1 N4 _) v( L" f! t1 ~6 \" D9 c tc=isempty(setdiff([1:n],p));% N1 O0 o7 \0 e( C8 A" F
if tc ( m5 V0 _1 X J! {+ w8 i2 r# }. P t0=sum(t(1,==3);- t4 c0 U# e6 L3 f4 J1 e/ }& e
if t0>=2 7 }% I6 |/ F' d4 a7 U: }5 S( L8 l nc=union(nc,1); $ b' O, K" y) ?7 n4 r4 x end% l0 c6 T" ?6 w; U# ?/ I- |& a
break;3 g5 y* h5 k! D3 c# Q" j3 Y
end) y3 F3 Z$ Q1 |
end & G/ F5 ]) t. o) ` z% \0 H5 H end; U3 T& k# A* N2 Q/ H) ?) C! k
0 [( `- z8 H9 v n- c. ?
; m& B% ?) j( i$ q$ l- g9 q
end