#include <iostream>
using namespace std;

//图定义
int arc[101][101]={0};
int visited[101]={0};
int low[101] = {0};
int counts=0;
int total[101]={0};
int nodes=0;
int mins=0;

int next(int v)
{
	for(int i=arc[v][0];i<=nodes;i++)
	{
		if(arc[v][i] != 0)
		{
			arc[v][0] = i + 1;
			return i;
		}
	}

	return 0;
}

void DFS(int v0)
{
	int p=0,w;
	visited[v0] = mins = ++counts;
	for(p=next(v0); p!=0;p=next(v0))
	{
		w=p;
		if(visited[w] == 0)
		{
			DFS(w);
			if(low[w] < mins) 
				mins = low[w];
			if(low[w] >= visited[v0])
				total[v0]=1;
		}
		else if(visited[w] < mins) 
			mins = visited[w];
	}
	low[v0] = mins;
}

void Finds()
{
	counts=1;
	visited[1] = 1;
//	low[1] = 1;
	for(int i=2;i<=nodes;++i)
	{
		visited[i] = 0;
	}
	int p = next(1);
	int v = p;
	DFS(v);

	if(counts < nodes)
	{
		total[1]=1;
		p=next(1);
		while(p!=0)
		{
			v = p;
			if(visited[v] == 0)
				DFS(v);
			p = next(1);
		}
	}
}

int main()
{
	int i,f,t,c=0;
	char h;
	scanf("%d",&nodes);
	while(nodes!=0)
	{
		counts=0;mins=0;
		for(i=0;i<=nodes;i++) arc[i][0]=1;
		scanf("%d",&f);
		while(f!=0)
		{
			while(scanf("%d%c",&t,&h))
			{
				arc[f][t] = 1;
				arc[t][f] = 1;
				if(h=='\n')
					break;
			}
			scanf("%d",&f);
		}

		Finds();

		for(i=1;i<=nodes;i++)
			if(total[i])
				c++;
		cout<<c<<endl;
		c=0;
		memset(total,0,sizeof(total));
		memset(low,0,sizeof(low));
		memset(visited,0,sizeof(visited));
		memset(arc,0,sizeof(arc));
		counts=0;mins=0;
	    scanf("%d",&nodes);
	}
	return 0;
}

• Re:做了好几天了~~~~还是WA，请教高手帮我看看 (1844) jsjhoubo 2007-12-13 21:32:25