无向图关键边(dfs邻接阵)
//无向图的关键边,dfs邻接阵形式,O(n^2)
//返回关键边条数,key[][2]返回边集
//传入图的大小n和邻接阵mat,不相邻点边权0
#define MAXN 100
void search(int n,int mat[][MAXN],int* dfn,int* low,int now,int& cnt,int key[][2]){
int i;
for (low[now]=dfn[now],i=0;i<n;i++)
if (mat[now][i]){
if (!dfn[i]){
dfn[i]=dfn[now]+1;
search(n,mat,dfn,low,i,cnt,key);
if (low[i]>dfn[now])
key[cnt][0]=i,key[cnt++][1]=now;
if (low[i]<low[now])
low[now]=low[i];
}
else if (dfn[i]<dfn[now]-1&&dfn[i]<low[now])
low[now]=lev[i];
}
}
int key_edge(int n,int mat[][MAXN],int key[][2]){
int ret=0,i,dfn[MAXN],low[MAXN];
for (i=0;i<n;dfn[i++]=0);
for (i=0;i<n;i++)
if (!dfn[i])
dfn[i]=1,bridge(n,mat,dfn,low,i,ret,key);
return ret;
}