2553.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"
#include"list"
using namespace std;
long sign[5010];
long st[5010],s;
long ok[5010];
long v;
list<int> out[5000],in[5000];
void find(int a)
{list<int>::iterator iter;
	
	sign[a]=1;
	
	for(iter=out[a].begin();iter!=out[a].end();iter++)
	{
		if(sign[*iter]==0)find(*iter);
	}
	st[s++]=a;
}
int sink;
void find_too(int a)
{list<int>::iterator iter;
	sign[a]=sink;	
	for(iter=in[a].begin();iter!=in[a].end();iter++)
	{	
		if(sign[*iter]!=0&&sign[*iter]!=sink)ok[sign[*iter]]=1;					   
		if(sign[*iter]==0)find_too(*iter);		
	}	
}
int main()
{long e,i,a,b;
	while(1)
	{
		scanf("%ld",&v);
		if(v==0)break;
		scanf("%ld",&e);		
		for(i=0;i<v;i++)
		{
			out[i].clear();
			in[i].clear();
		}
		//mset(edge,0,sizeof(char)*5000*5000);
		for(i=0;i<e;i++)
		{
			scanf("%ld %ld",&a,&b);
			if(a!=b){
				out[a-1].push_back(b-1);
				in[b-1].push_back(a-1);
			}
		}
		s=0;
		 memset(sign,0,sizeof(long)*5010);
		 for(i=0;i<v;i++)
			 if(!sign[i])find(i);
		 memset(sign,0,sizeof(long)*5010);
		 memset(ok,0,sizeof(long)*5010);		 
		 sink=1;
		 for(i=v-1;i>=0;i--)
		 {	 
			 if(sign[st[i]]==0)
			 {find_too(st[i]);
				sink++;
			 }
		 }
		 int key;
		 for(i=0,key=0;i<v;i++)
		 {	 if(ok[sign[i]]==0){if(key)printf(" ");
								
								else key=1;
							
							printf("%ld",i+1);
				 
							}
		 }
		 printf("\n");		
	}
	return 0;
}