#include<stdio.h>
const int MAXL = 100 ;

int  net[MAXL][MAXL]={0};
int  pre[MAXL] ={0};
char stack[MAXL];
int  top = -1 ,n,m;

int Isempty(void)      // if is stack is empty ,then return 1 ,while return 0 in contrast 
{
	if( top <0 )return 1;
	return 0;
}

char pop(void)     // pop an element out of stack
{
	return stack[top--];
}

void push( char temp )   // push an element into stack
{
	stack[++top] = temp;
}

void ini( void )     // init 
{
	int i , j;
	for ( i = 1;i <= n;i ++)
	{
		pre[i] = 0;
		for ( j= 1;j <= n;j ++)
			net[i][j] = 0;
	}
	top = -1;
}

int find_MAX( void )  // find the max of rest number ,if more than 1 was found ,then return -1;
{
	int i , k=0 , z = 0 ;
	for ( i = 1; i<= n ;i ++)
		if( !pre[i] && pre[i] != -1 ){ k ++ ; z = i;}
	if( k != 1 )return -1;
	return z;
}


int DFS ( int x , int y )////////////////////////////////////DFS
{
	int A[MAXL*MAXL]={x},len = 0,i,t;
	int vis[MAXL]= {0};
	while( len != -1 )
	{
		t = A[len --];
		if( vis[ t ] ) continue;
		vis [t] = 1;
		if( pre[t] >0 )
		{
			for ( i = 1;i <= n ;i ++ )
			{
				if( net[t][i] )
				{
					if ( i == y ) return 1;
					A[++len] = i;
				}
			}
		}
	}
	return 0;
}



int Judge( void )     //if yield error ,return 0 ,else return 1
{
	int  p , q;
	char s[5];
	scanf("%s",s );
	p = s[0] - 'A' + 1;
	q = s[2] - 'A' + 1;
	if( p == q )  return 0;
	if ( s[1] == '<' )
	{
		if( DFS( q , p ))return 0;
		net[p][q] ++;
		pre[p] ++;   
		return 1;
	}
	if( s[1] == '>' )
	{
		if( DFS ( p , q )) return 0;
		net[q][p]  ++;
		pre[q] ++;
		return 1;
	}
	return 1;
}

int solve ( void )
{
	int i , j ,t;
	int a[MAXL][MAXL],b[MAXL];
	for ( i = 1;i <= n;i ++)
	{
		b[i] = pre[i]; 
		for( j = 1;j <= n;j ++)
			a[i][j] = net[i][j];
	}
	for ( i= 1;i <= n;i ++)
	{
		t = find_MAX();pre[t] = -1;
		if ( t == -1) goto loop;
		push(t + 'A' - 1 );
		for ( j = 1 ;j <= n; j ++ )
			 if( net[j][t])
			 {
				 pre[j] -= net[j][t] ;
				 net[j][t] = 0;
			 }
	}
	for ( i = 1;i <= n;i ++)
	{
		pre[i] = b[i];
		for ( j= 1;j <= n;j ++)
			net[i][j] = a[i][j];
	}
	return 1;
loop:
	for ( i = 1;i <= n;i ++)
	{
		pre[i] = b[i];
		for ( j= 1;j <= n;j ++)
			net[i][j] = a[i][j];
	}
	return 0;
}


int main ( void )
{
	int i  , err , flag;
	char s[4];
	scanf("%d%d",&n , &m);
	while ( n + m != 0)
	{
		ini();
		err = 0; flag =0;
		for ( i = 1;i <= m;i ++)
		{
			if( err ) scanf("%s",s);
			else if( Judge() )
			{
				if( !flag && i >= n-1)
				{
					if(solve()) flag = i;
					else top = -1;
				}
			}
			else err = i;
		}
		if( err )
			printf("Inconsistency found after %d relations.\n",err);
		else if( flag)
		{
			printf("Sorted sequence determined after %d relations: ",flag);
			while(!Isempty())
				printf("%c",pop());
			printf(".\n");
		}
		else
			printf("Sorted sequence cannot be determined.\n");
		scanf("%d%d",&n , &m );
	}
	return 0;
}

• Re:还没有查出什么错来,哪位高人指点一下！！！ (13) hust_acm 2004-10-25 16:10:46
  • Re:还没有查出什么错来,哪位高人指点一下！！！ (102) hujk2008 2004-10-25 16:32:07
    • 数据里你错了一组，答案是可以的，你说是inconsistency (128) hawk 2004-10-25 16:39:41
      • Re:数据里你错了一组，答案是可以的，你说是inconsistency (15) hust_acm 2004-10-25 18:51:13
• 打扰了各位，原来我弄错了题目的意思！！！！衰^^^^^^^^^^^^^^^^下面已经改好了！ (679) hujk2008 2004-10-25 18:20:14
  • 谢谢hawk^_^ (0) hujk2008 2004-10-25 18:24:14