大意：给你一些关系，输出拓扑序列，如果有环，讨论一下；如果有多种情况，讨论一下；如果那两种都不是，输出拓扑序列。
思路：没什么好说的，就是一个求拓扑序列。
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <limits.h>
#include <algorithm>
#define LL long long
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
int Map[30][30], dis[30], Ans[30], tem[30];
int Topo()
{
stack<int>s;
memcpy(tem, dis, sizeof(dis));
for(int i = 0; i < n; i++)
{
if(!tem[i])
{
s.push(i);
}
}
int cnt = 0;
bool flag0 = false;
while(!s.empty())
{
if(s.size() > 1)
{
flag0 = true;
}
int temp = s.top();
Ans[cnt++] = temp;
s.pop();
for(int i = 0; i < n; i++)
{
if(Map[temp][i] && --tem[i] == 0)
{
s.push(i);
}
}
}
if(cnt != n)
{
return 1;
}
else if(flag0)
{
return 2;
}
return 0;
}
void Solve()
{
while(~scanf("%d%d", &n, &m) && (n ||m))
{
bool flag1 = false, flag2 = false;
memset(Map, 0, sizeof(Map));
memset(dis, 0, sizeof(dis));
for(int i = 1; i <= m; i++)
{
char str[3];
scanf("%s", str);
if(!flag1 &&!flag2)
{
if(Map[str[2]-‘A‘][str[0]-‘A‘] == 1)
{
flag2 = true;
printf("Inconsistency found after %d relations.\n", i);
continue;
}
if(!Map[str[0]-‘A‘][str[2]-‘A‘])
{
Map[str[0]-‘A‘][str[2]-‘A‘] = 1;
dis[str[2]-‘A‘]++;
}
int flag = Topo();
if(!flag)
{
printf("Sorted sequence determined after %d relations: ", i);
for(int j = 0; j < n; j++)
{
printf("%c", Ans[j]+‘A‘);
}
printf(".\n");
flag1 = true;
}
else if(flag == 1)
{
printf("Inconsistency found after %d relations.\n", i);
flag2= true;
}
}
}
if(!flag1 &&!flag2)
{
printf("Sorted sequence cannot be determined.\n");
}
}
}
int main(void)
{
Solve();
return 0;
}