题目描述：
有8头牛，给出n条信息，每条信息要求牛X要在牛Y旁边。
再按他们的字典序最小的输出。
分析： 先按字典序把这8头牛用1~8表示。然后记录信息，即谁在谁旁边。
用pair存在他旁边的牛的序号。首先初始化把每头牛的first改成他自己，如果这个牛的first==他自己，那么可以发现，他只要求旁边有一头指定的牛，所以他一定是他所在团体的顶端或者末端。我们就找出了端点，把端点排序，从一个端点开始，依次把他的团体全部输出。可以一直往??走，直到走到端点为止。比如1-1-3，1-3-4，3-4-4。从1到3再到4。（中间的点表示当前的位置，左右表示pair中含有的数）如果3中1和4位置换一下，变成1-1-3，4-3-1，4-2-2。先把输出过的用一个used数组标记一下，避免重复输出。如果1走到3后往??走，读取的是1，1已经输出过，而且3不是端点，就读取左边的4往4走，同样可以输出1，3，4。
至于存入pair，我是如果如果右边没有数字就先存进右边，比如6-6-0存入5变成6-6-5.如果右边有数字，还要存进去，说明他不是端点，就存入左边。比如变成4-6-5。
代码：
#include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <map> using namespace std; typedef long long ll; int n; char s[106]; pair<int,int> p[9]; vector<int> ans; char str[9][20]={"","Beatrice","Belinda","Bella","Bessie","Betsy","Blue","Buttercup","Sue"}; void init() { for(int i=0;i<=8;i++) { ans.push_back(i); p[i].first=i; } } int find(char s[]) { for(int i=1;i<=8;i++) { if(strcmp(s,str[i])==0) { return i; } } return 0; } bool used[9]; void prin(int i) { int k; k=i; if(!used[k]) { printf("%s\n",str[k]); used[k]=true; } } void swap(int i) { if(!(p[i].first==i)) { if(p[i].first>p[i].second) { int t=p[i].second; p[i].second=p[i].first; p[i].first=t; } } } int main() { int n; cin>>n; init(); vector<int> pop; for(int i=0;i<n;i++) { char s1[20],s2[20]; scanf("%s must be milked beside %s",s1,s2); int a,b; a=find(s1); b=find(s2); if(a>b) { int t=a; a=b; b=t; } if(!p[a].second) { p[a].second=b; } else { p[a].first=b; } swap(a); if(!p[b].second) { p[b].second=a; } else { p[b].first=a; } swap(b); } for(int i=1;i<=8;i++) { if(p[i].first==i) pop.push_back(i); } sort(pop.begin(),pop.end()); for(int i=0;i<pop.size();i++) { if(p[pop[i]].second&&!used[p[pop[i]].second]) { int k=pop[i]; while(p[k].second||p[k].first!=k) { prin(k); if(!used[p[k].second]) { k=p[k].second; } else if(!used[p[k].first]) { k=p[k].first; } else { break; } } prin(k); } else { if(!used[pop[i]]) { printf("%s\n",str[pop[i]]); used[pop[i]]=true; } } } return 0; }
原文：https://www.cnblogs.com/studyshare777/p/12405209.html