题目的意思是给你一个偏序关系集,问这个关系是否是良序的。使用了拓扑排序。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int map[26][26];
int op_m[26][26];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int count[26];
int op_c[26];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char road[26];
int len;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int que[1000];
int head, tail;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initq ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
head = 0;
tail = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inq ( int *in )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
que[++tail] = *in;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void outq ( int *out )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
*out = que[head++];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int gets ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return tail - head + 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[i][j] = 0;
}
count[i] = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void cpy ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
op_m[i][j] = map[i][j];
}
op_c[i] = count[i];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void add ( char a, char b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if ( ! map[ a-'A' ][ b-'A' ] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[ a-'A' ][ b-'A' ] = 1;
count[ b-'A' ] ++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int sort ( int n ) /**//*排序返回结果:1成功, 0有环,-1有多种情况*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int out;
int flag = 1;
len = 0;
initq ();
cpy ( n );
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! op_c[i] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
inq ( &i );
op_c[i] = -1;
}
}
while ( gets () )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( gets () > 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
flag = 0;
len = 0;
}
outq ( &out );
if ( flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
road[len++] = out + 'A';
}
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( op_m[out][i] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
op_m[out][i] = 0;
op_c[i] --;
}
}
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! op_c[i] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
inq ( &i );
op_c[i] = -1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
flag = 1;
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( op_c[i] > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
flag = 0;
break;
}
}
if ( ! flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 0;
}
if ( len < n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return -1;
}
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n, m;
char in[5];
int flag;
int ans;
while ( scanf ( "%d%d", &n, &m ) != EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( n==0 && m ==0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
init ( n );
flag = 1;
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%s", &in );
if ( ! flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
continue;
}
if ( in[0] == in[2] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "Inconsistency found after %d relations.\n", i+1 );
flag = 0;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
add ( in[0], in[2] );
ans = sort ( n );
if ( ! ans )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "Inconsistency found after %d relations.\n", i+1 );
flag = 0;
}
else if ( ans == 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
road[len] = '\0';
printf ( "Sorted sequence determined after %d relations: %s. \n", i+1, road );
flag = 0;
}
}
}
if ( flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "Sorted sequence cannot be determined.\n" );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
地址:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094