function [nc] = ncutf(g) 9 l7 |- @3 \! S- u/ |8 v& k%求割点的算法 g为邻接矩阵 nc为割点的集合6 Z! k1 s Q; i6 g3 a) I
n=size(g,1);2 @' f3 D$ I" i: U) I* I: d
if n>=3 4 G1 T2 Q. L' i& b" G2 A' B a=sum(g);0 q9 ~ ^* f# w6 w/ W0 y3 ?& p
b=sum(a==2); # P" n) ]- u" k/ S& h9 {9 c4 _ if b==n' h( [1 m; \. e/ M. a! M& ~
fprintf('本图为圈,无割点。n') 8 n% g1 |7 Z1 X% w) k nc=0;. @2 n' w1 B$ N6 B
end$ N3 Z/ C( _) \
else) P" w& Q* [! H2 M7 D6 l# S1 j$ L; p
[w,k]=dfs3(g);! b% \( y+ A2 L
%nc=[]; F- B5 u; U0 x' T' V; V
nc=isncf(w,k);" a$ y+ e4 C7 U7 Q6 j
n=size(g,1);& e; l5 q2 c& b0 F
for i=1:n2 X( k; _$ H# S' i) ] R+ u, g
for j=1:n8 K6 n# {/ O* i5 s& Z
if w(i,j)>1 ! o/ g2 x- K2 V$ B if k(i)>k(j). z( K9 g ^; o% h. U8 A$ w8 f+ l
g(i,j)=2;9 \% _2 C! s, H# p+ C3 V2 I- U* H
else/ h8 |4 z* f- X# ]# [' T
g(i,j)=3; 0 J2 b5 q; T1 ~! y- Y9 z9 n$ T end & ~- B$ }( I: r$ q" [ end ! F* e! j7 ~0 K1 q9 ?% f4 t end, Y/ q, V2 m# W, F: h" q
end: c- p' B# I* C6 z
. ?) W' D0 f/ I. u/ w; }2 o8 e for i=1:n. P- o1 p+ o: s. J6 E' t
f1=find(g(i,==2);. A$ k6 u4 u% y) u7 e& s
f2=find(g(i,==3);* O1 s0 D, |3 E- z* Q
f=union(f1,f2);& v+ q8 B3 {/ W8 x
l(i)=min([k(f) k(i)]); % v5 m& F" L. c8 y7 L: k- } end$ f8 n, N( D( }1 f* X
* j* X9 Z: H7 L8 C for i=1:n 2 |* w( _% P$ g, c, P for j=1:n 0 ~) p; h* _( L. J h; i if g(i,j)==3 & k(i)>1&l(j)>=k(i)% ^' F2 U, L; n' w- E O, q
nc=union(i,nc); + M) Z2 z* \: y# N! F4 m8 V7 W end: Y6 R- c+ n# s0 \0 U
end . p v, C9 l" H" @ end& X6 V# ?1 h8 u, Y2 R- O
end7 C: h) z' T4 ^: p% v+ j
end! X7 i" _' P" P. S* I" v
7 V8 R/ H, E! T; c ! U+ T9 _) C7 \2 l2 B. L' mfunction nc=isncf(w,k) 2 b9 ~9 _6 |6 D: D3 M) ^ f3 c nc=[]; : O: p3 n" a6 X, P% V t=zeros(size(w));7 \! K; s6 R- ]& q" ]9 ~' }6 M
n=size(w,1);! G( S2 D& p9 }
a=find(w~=0); 2 m% R& x+ X( s- _7 W* W* v- ? for i=1:length(a)' j: A9 r. |# N2 o7 U5 g$ y+ q
d(i)=w(a(i)); ]" o% E* } ^9 G; l& R
if a(i)/n>floor(a(i)/n) % G* Z; A( j- y t(i)=floor(a(i)/n)+1;+ }- o% p, b7 h' H
else# Y+ [( {' v5 ~+ x2 Q0 x7 ^% g
t(i)=floor(a(i)/n);( k" e& v0 L( T3 k- |/ s) V
end * h% S1 q, t3 @4 |7 | t1(i)=mod(a(i),n);3 c' K: `) q/ }$ ^
if t1(i)==0 0 W" J" k% j8 l- E0 u d t1(i)=n; ) ^; f8 c N. p8 c: a/ { end $ S0 H! U) n+ `' h" d end 0 @8 k, \' ~- k. N( ]2 T8 V. \ [b,c]=sort(d);0 T" J% q( `& U2 [
p=[1];pc=0; , E. b# Q0 }! w9 _& N$ n for i=1:length(a)8 X; c+ B: g% K3 i% e- s: e6 g( w( d( O
if k(t1(c(i)))<k(t(c(i))) # ~+ a V% w h: V% r$ t p=union(p,t(c(i)));3 [+ J$ \& e+ f1 _% C( r
t(t1(c(i)),t(c(i)))=3; 2 L. u6 f. L" e: f% X end 2 i. r# F3 J- E' O7 T5 R if pc==0# r) R4 `$ o# E: w
tc=isempty(setdiff([1:n],p)); ( }4 I! b* {8 ] if tc 7 R1 O$ p: ~+ g- [/ f t0=sum(t(1,==3); 8 o1 q3 c" q' _' q3 }( w3 t7 z if t0>=28 B! C- W, U$ H7 R; B
nc=union(nc,1);1 X+ J p# ?6 F8 d
end " u6 z* Y) I" d- d- }5 f1 M break; 6 ~+ ~9 `% s/ R4 [. b end 7 f p3 t$ s& }: E* j1 b% U [+ l end 0 h5 c, V, U5 t& P! B end $ a" q+ t d3 I4 W3 c ) ?( d: P8 J2 T% h) t% v