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