ABC 有三个数，分别用A，B，C表示，告诉你他们的两两比较的结果，输出他们的大小关系。Input输入的数据有多组，每组数据有三行，每行有两个字母，表示前面的字母代表的数比后面的字母代表的数大,每行的两个字母不相同。Output如果他们比较的结果合法，那么把它们按照从小到大的顺序输出，两个字母中间应有“<”号，否则就输出“The input is not true!”,输出占一行。 Sample Input AB BC AC AB BA AC Sample Output C<B<A The input is not true!
既然是字母比较，那么拓扑排序就能很好解决这个问题。为什么？ 因为拓扑排序是有向无环图，他的实质是对有向图的顶点排成一个线性序列。简单来说。由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
回到问题，我们需要的结果恰好就是一个序列，我们的输入可以看作是拓扑排序给定的先后顺序。且当成环时（AB BC CA），就会无法拓扑排序也就是ABC无法比较。
那么怎么排序呢？ 首先我们需要处理输入的数据，就拿AB BC AC 举例子
AB相当于 A>B,由于我们的输出是从小到大 所以，姑且想象成B->A（此时A的入度需要+1，拓扑排序根据入度依次删除节点） 同时记录下B的可去的一个节点增加一个A
同理BC 就是B的入度+1，C的可去的一个节点增加一个B
最后AC 就是A的入度+1，C的可去的一个节点增加一个A
然后开始进行拓扑排序： 现在A的入度为2，B的入度为1，C的入度为0 找到C，删去它，并且找到它的可去的节点（C->A 和C->B）使A,B入度-1；
现在A的入度为1，B的入度为0，C已被处理 找到B，删去它，并且找到它的可去的节点（B->A）使A入度-1；
现在A的入度为0，B已被处理，C已被处理 找到A，删去它，发现他没有可去的节点，那么抵达末尾，循环结束；
因为有三个节点，所以如果我们循环三次说明是正确的。 然后按照删除节点的顺序打印C->B->A即可
以上便是
正常结果的情况
下面看看如果不是正确结果的情况
如果没有循环三次，说明他可能成环了，（AB BA AC） 经过上面同理处理，A入度为2，可去节点为B；B入度为1，可去节点为A； C入度为0可去节点为A 那么先删去C，然后使A入度-1，那么此时无入度为0的点跳出循环。
你可能会问若第三条不是AC而是BC呢？那会变成B的入度为2，然后先删C，B入度-1，还是没有入度为0的点。
接下来我们考虑一下特殊输入，比如AB出现两次，那么我们就需要让多余的数据不处理
还有就是一个节点指向两个节点，另外两个节点不知道顺序的情况（AB AB CB）B入度为0，但是AC入度均为1.所以没有入度为2的节点需要提前结束循环判为错误，因为我们的题目需要保证ABC存在绝对比较性
好了，下面是代码时间：
#include<iostream> #include<bits/stdc++.h> using namespace std; struct ABC{ char u;//自身所代表字母 int d;//入度 vector<int> v;//存比它大的字母 }e[3];//ABC分别对应三个点 queue<ABC> q; char res[4]; bool used(vector<int> v,int x)//判断vector是否存在x { for(vector<int>::iterator i=v.begin();i!=v.end();i++) { if(*i==x) { return true; } } return false; } int main() { int n=0; char x[3],y[3],z[3]; e[0].u='A'; e[1].u='B'; e[2].u='C'; //初始化ABC while(~scanf("%s%s%s",&x,&y,&z)) { e[x[1]-'A'].v.push_back(x[0]-'A'); e[x[0]-'A'].d++; if(!used(e[y[1]-'A'].v,y[0]-'A'))//如果没有加入到vector才加入，删去重复输入 { e[y[1]-'A'].v.push_back(y[0]-'A'); e[y[0]-'A'].d++; } if(!used(e[z[1]-'A'].v,z[0]-'A')) { e[z[1]-'A'].v.push_back(z[0]-'A'); e[z[0]-'A'].d++; } for(int i=0;i<3;i++)//获取入度为0的字母 { if(!e[i].d) { q.push(e[i]); break; } } int sum=0; while(!q.empty())//BFS { ABC temp=q.front(); res[sum++]=temp.u;//记录结果 q.pop(); if(temp.v.size()==2) { //如果某个点 和两个点连接 且那两个点的权值相等，说明两个点无法比较大小 if(e[temp.v[0]].d==e[temp.v[1]].d) break; } for(vector<int>::iterator i=temp.v.begin();i!=temp.v.end();i++) { if(!(--e[*i].d))//所连线边入度-1，且如果其入度为0，就加入队列 q.push(e[*i]); } } if(sum==3)//如果有三次则说明ok { cout<<res[0]<<"<"<<res[1]<<"<"<<res[2]<<endl; } else{ puts("The input is not true!"); } for(int i=0;i<3;i++)//重置e { e[i].d=0; e[i].v.clear(); } } }