#include<stdio.h>
#include<stdlib.h>
#define MAX 1000
int matrix[MAX+1][MAX+1];
int visited[MAX+1];
int hasspf;
int vexnum;
int firstadjvex(int u)
{
	int j;
	for(j=1;j<=MAX;j++)
		if(matrix[u][j])
			return j;
	return -1;
}
int nextadjvex(int u,int w)
{
	int j;
	for(j=w+1;j<=MAX;j++)
		if(matrix[u][j])
			return j;
	return -1;
}
void DFS(int v)
{
	int w;
	visited[v]=1;
	for(w=firstadjvex(v);w>=0;w=nextadjvex(v,w))
		if(!visited[w])
			DFS(w);
}
int findunvisited(int j)
{
	int i;
	for(i=1;i<=vexnum;i++)
		if(!visited[i]&&i!=j)
			return i;
	return -1;
}
int is_spf(int j)
{
	int temp[MAX+1];
	int i,num,w,v;
	for(v=1;v<=vexnum;v++)
		visited[v]=0;
	for(i=1;i<=vexnum;i++)
	{
		temp[i]=matrix[j][i];
		matrix[j][i]=0;
	}
	num=0;
	while((w=findunvisited(j))!=-1)
	{
		num++;
		DFS(w);
	}
	for(i=1;i<=vexnum;i++)
		matrix[j][i]=temp[i];
	return num;
}

int init()
{
	int from,to;
	int i,j;
	for(i=1;i<MAX;i++)
		for(j=1;j<MAX;j++)
			matrix[i][j]=0;
	vexnum=0;
	scanf("%d",&from);
	if(from==0)
		return 0;
	while(from)
	{
		if(from>vexnum)
			vexnum=from;
		scanf("%d",&to);
		if(to>vexnum)
			vexnum=to;
		matrix[from][to]=1;
		matrix[to][from]=1;
		scanf("%d",&from);
	}
	return 1;
}
main()
{
	int i,j;
	int nsnet;
	j=i=0;
	while(init())
	{
		i++;
		printf("Network #%d\n",i);
		hasspf=0;
		for(j=1;j<=vexnum;j++)
		{
			nsnet=is_spf(j);
			if(nsnet>1)
			{
				printf("  SPF node %d leaves %d subnets\n",j,nsnet);
				hasspf=1;
			}
		}
		if(!hasspf)
			printf("  No SPF nodes\n");
	}
}

• Re:我觉得没错啊,怎么减少内存开销啊???? (1824) yygy 2008-10-19 14:33:41
• Re:我觉得没错啊,怎么减少内存开销啊???? (7) yygy 2008-10-19 14:35:01