无向图块(bfs邻接阵形式).txt

ACM资料大集合

//无向图的块,dfs邻接阵形式,O(n^2)
//每产生一个块调用dummy
//传入图的大小n和邻接阵mat,不相邻点边权0
#define MAXN 100

#include <iostream.h>
void dummy(int n,int* a){
	for (int i=0;i<n;i++)
		cout<<a[i]<<' ';
	cout<<endl;
} 

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<n;i++)
		if (mat[now][i]){
			if (!dfn[i]){
				search(n,mat,dfn,low,i,cnt,st,sp);
				if (low[i]<low[now])
					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])
				low[now]=dfn[i];
		}
}

void block(int n,int mat[][MAXN]){
	int i,cnt,dfn[MAXN],low[MAXN],st[MAXN],sp=0;
	for (i=0;i<n;dfn[i++]=0);
	for (cnt=i=0;i<n;i++)
		if (!dfn[i])
			search(n,mat,dfn,low,i,cnt,st,sp);
}