TXT

else if (dfn[i]

By Joanne Lewis,2014-11-01 10:46
10 views 0
else if (dfn[i]

else if (dfn[i]

low[now]=dfn[i];

}

}

int key_vertex(int n,int mat[][MAXN],int* key){

int ret=0,i,cnt,rd,dfn[MAXN],low[MAXN],bb[MAXN];

for (i=0;i

for (cnt=i=0;i

if (!dfn[i]){

rd=0;

search(n,mat,dfn,low,i,ret,key,cnt,i,rd,bb);

if (rd>1&&!bb[i])

key[ret++]=i,bb[i]=1;

}

return ret;

}

//无向图的块,dfs邻接阵形式,O(n^2)

//每产生一个块调用dummy

//传入图的大小n和邻接阵mat,不相邻点边权0

#define MAXN 100

#include

void dummy(int n,int* a){

for (int i=0;i

cout<

cout<

}

void search(int n,int mat[][MAXN],int* dfn,int* low,int now,int& cnt,int* st,int&

sp){

int i,m,a[MAXN];

dfn[st[sp++]=now]=low[now]=++cnt;

for (i=0;i

if (mat[now][i]){

if (!dfn[i]){

search(n,mat,dfn,low,i,cnt,st,sp);

if (low[i]

low[now]=low[i];

if (low[i]>=dfn[now]){

for (st[sp]=-1,a[0]=now,m=1;st[sp]!=i;a[m++]=st[--sp]);

dummy(m,a);

}

}

else if (dfn[i]

low[now]=dfn[i];

}

}

void block(int n,int mat[][MAXN]){

int i,cnt,dfn[MAXN],low[MAXN],st[MAXN],sp=0;

Report this document

For any questions or suggestions please email
cust-service@docsford.com