题意：给你m个类似于 A < B 的条件，让你判断可不可以确定一个大小关系。
分为以下三种。
Sorted sequence determined after xxx relations: yyy...y. Sorted sequence cannot be determined. Inconsistency found after xxx relations.
1是完全确定大小关系，输出一句话 + 需要的多少个关系来确定。
2是所有条件都不能完全确定一个大小关系。即最后只能是偏序关系。
3是处理到多少个关系后发现矛盾，反映到图中，是图中存在了环。
思路：每次输入一个关系后，进行一次拓扑排序。注意要另开一个入度数组。
AC Code：
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<stack> #include<cmath> #include<cstdio> #include<iomanip> #include<sstream> #include<algorithm> using namespace std; #define read(x) scanf("%d",&x) #define Read(x,y) scanf("%d%d",&x,&y) #define sRead(x,y,z) scanf("%d%d%d",&x,&y,&z) #define gc(x) scanf(" %c",&x); #define mmt(x,y) memset(x,y,sizeof x) #define write(x) prllf("%d\n",x) #define INF 0x3f3f3f3f #define ll long long #define mod 998244353 #define pdd pair<double,double> const int N= 1e5+5; int head[100],tot; struct Edge { int next; int to; }edge[10000]; int deg[50]; int a[50],cnt;int du[50]; inline void add(int from,int to) { edge[++tot].next = head[from]; edge[tot].to = to; head[from] = tot; deg[to] ++; } inline void init() { mmt(head,-1); mmt(deg,0); cnt = tot = 0; } int topsort(int n) { memcpy(du,deg,sizeof(deg)); cnt = 0; bool r= 1; queue<int> Q; for(int i = 1;i <= n;++i) if(deg[i] == 0) Q.push(i); while(Q.size()){ int x= Q.front(); if(Q.size()>=2) r = 0; Q.pop(); a[++cnt] = x; for(int i = head[x];~i;i = edge[i].next){ int y = edge[i].to; if(--du[y] == 0) Q.push(y); } } if(cnt < n) return -1;//有环存在 else if(r == 1) return 1;//全序 else return 0;// 偏序 } int main() { //freopen("input.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m) == 2&&n+m){ char u,v;char op; init(); int flag = 0; int num = 0; for(int i = 1;i <= m;++ i){ cin>>u>>op>>v; int f = u - 'A' +1; int t = v - 'A' + 1; add(f,t); if(flag == -1 || flag == 1) continue; if(topsort(n) == 1) { flag = 1; num = i; } else if(topsort(n) == -1){ flag = -1; num = i; } else { if(topsort(n) == 0){ flag = 0; } } } if(flag == 1){ printf("Sorted sequence determined after %d relations: ",num); for(int i = 1;i <= n;++i) { cout<<char(a[i] + 'A' - 1); } cout<<'.'<<endl; } else if(flag == -1){ printf("Inconsistency found after %d relations.\n",num); } else puts("Sorted sequence cannot be determined."); } }
