///pku 1144 Newwork
////WA

#include<stdio.h>

typedef struct Node
{
	bool visited;
	char value;
	struct Node *next;
}* node;

char criticalnum=0;
node a[101];
int nodenum=0;
bool find=false;
bool iscriticalnode=false;

bool readin()  //if the last line 0,stop do,return false .Every time solve one block
{
	int i;
	char ch;
	scanf("%d",&nodenum);
	i=nodenum;
	if(nodenum==0)
	{
		return false;
	}

	for(i=0;i<=nodenum;i++)
	{
		a[i]=new struct Node;
		a[i]->visited=false;
		a[i]->value=i;
		a[i]->next=NULL;
	}
	getchar();   ////ignore the blank after the first line that expresses the nodenum
	while(i>0)
	{
		char first;
		i--;
		scanf("%c",&ch);
		if(ch=='0')
		{
			break;
		}
		first=ch-48;
	//	a[first]=new struct Node;
		a[first]->value=first;
		a[first]->next=NULL;

		while(scanf("%c",&ch),ch!='\n')////read one line
		{
			if(ch==' ')
				continue;
			ch=ch-48;
			node temp,temp1;
			temp=new struct Node;
			temp->value=ch;
			temp->next=a[first]->next;
			a[first]->next=temp;

			temp1=new struct Node;
			temp1->value=a[first]->value;
			temp1->next=a[ch]->next;
			a[ch]->next=temp1;
		}
	}
	return true;
}

void CriticalNode(char num,char end,char remov)
{
	if(find==true||a[num]->value==end)
	{
		find=true;
		return ;
	}
	if(num==remov)
	{
		return;
	}

	node p=a[num]->next;
	a[num]->visited=true;
	while(p!=NULL)
	{
		if(a[p->value]->visited==false)
			CriticalNode(p->value,end,remov);
		p=p->next;
	}

}

void print()
{
	for(int i=1;i<=nodenum;i++)
	{
		node p=a[i];
		while(p!=NULL)
		{
			printf("%d ",p->value);
			p=p->next;
		}
		printf("\n");
	}
}

int main()
{
	char i,j,k;
	
	while(readin())
	{
		
		
		criticalnum=0;
		for(k=1;k<=nodenum;k++)   ////remove k,see if it is critical node
		//	k=6;
		{
			for(int m=1;m<=nodenum;m++)
			{
				a[m]->visited=false;
			}
			iscriticalnode=false;
			find=false;
			for(i=1;i<=nodenum;i++)
			{
				for(int m=1;m<=nodenum;m++)
				{
					a[m]->visited=false;
				}
				if(i==k)
					continue;
				if(iscriticalnode==true)
					break;
				for(j=i+1;j<=nodenum;j++)
				{
					for(int m=1;m<=nodenum;m++)
					{
						a[m]->visited=false;
					}

					if(j==k)
					{
						continue;
					}
					find=false;
					CriticalNode(i,j,k);
					if(find==false)
					{
						iscriticalnode=true;
						criticalnum++;
				//		printf("k=%d\n",k);
						break;
					}

					
				}///end of for(j=i+1;j<=nodenum;j++)

			}///end of for(i=1;i<=nodenum;i++)
			iscriticalnode=false;			 
		}////end of for k
		printf("%d\n",criticalnum);
//		print();
	}
	return 0;
}

• Re:1144 测试数据都对，为啥WA？ (3031) lsg0827 2011-10-22 20:23:58