J. Kitchen Plates
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given 5 different sizes of kitchen plates. Each plate is marked with a letter A, B, C, D, or E. You are given 5 statements comparing two different plates, you need to rearrange the plates from smallest size to biggest size. For example: the sizes of these plates.
Input
The input consist of 5 lines. In each line there will be 3 characters, the first and last character will be either A, B, C, D, or E and the middle character will be either > or < describing the comparison between two plates sizes. No two plates will be equal.
Output
The output consist of 5 characters, the sorted order of balls from smallest to biggest plate. Otherwise, if the statements are contradicting print impossible. If there are multiple answers, print any of them.
Examples
input
D>B A>D E<C A>B B>C
output
ECBDA
input
B>E A>B E>A C<B D<B
output
impossible
题目的大体意思是输入五行，给出五个盘子的大小关系，然后需要输出从小到大的顺序，如果没有满足的情况，直接输出impossible
分析：这个题关键在于能够想到将两个点之间的大小关系转换为一条有向边，然后将所有的关系看作是一个DAG图，然后进行 拓扑排序 <—这是一篇比较不错的关于 拓扑排序 的博客
代码没什么，还是加上吧
Main_Code :
priority_queue <int, vector<int>, greater<int> > xiao; char ans[6]={' ','A','B','C','D','E'}; int deg[10]; map<char ,int > mp; int vis[10]; int Gra[10][10]; vector<int> vet; void Top_sort(){ for(int i=1;i<=5;i++){ if(deg[i]==0) xiao.push(i);///度数为0的节点 } while(!xiao.empty()){ int x = xiao.top(); xiao.pop(); vet.push_back(x); for(int i=1;i<=5;i++){ if(Gra[x][i]){ deg[i] --; if(deg[i]==0) xiao.push(i); } } } } int main(){ mp['A']=1,mp['B']=2,mp['C']=3,mp['D']=4,mp['E']=5; int T=5; for(int i=1;i<=T;i++){ string s;cin>>s; char a,b,c; a=s[0],b=s[1],c=s[2]; if(b == '<') swap(a,c); deg[mp[c]] ++;///入点度数加1 Gra[mp[a]][mp[c]] = vis[mp[a]] = vis[mp[c]] = 1;///已经到过这个点 } Top_sort(); if(vet.size()==5) { for(int i=4;i>=0;i--){ printf("%c",ans[vet[i]]); } } else{ cout<<"impossible"<<endl; } return 0; } /** D>B A>D E<C A>B B>C **/
