有向图最小点基(邻接阵形式)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】有向图最小点基(邻接阵形式)

作者:奕男 / 发布于2016/3/15/ 561

//有向图最小点基,邻接阵形式,O(n^2)
//返回电集大小和点集
//传入图的大小n和邻接阵mat,不相邻点边权0
//需要调用强连通分支
#define MAXN 100

int base_vertex(int n,int mat[][MAXN],int* sets){
	int ret=0,id[MAXN],v[MAXN],i,j;
	j=find_components(n,mat,id);
	for (i=0;i<j;v[i++]=1);
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			if (id[i]!=id[j]&&mat[i][j])
				v[id[j]-1]=0;
	for (i=0;i<n;i++)
		if (v[id[i]-1])
			v[id[sets[ret++]=i]-1]=0;
	return ret;
}

　　

试试其它关键字

同语言下

可能有用的

奕男贡献的其它代码(13)

Copyright © 2004 - 2024 dezai.cn. All Rights Reserved 站长博客粤ICP备13059550号-3