题目链接：点击打开链接
题目大意：略。
解题思路：字符串数组绑定下标 + 拓扑排序（邻接表）。
AC 代码
1.#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; vector<string> vec; // 存储字符串，为了匹配对应的位置 map<string,int> mp; // 记录是否访问过 const int MAXV=1000; // mk：匹配字符串的位置 // inrr：存取入度 // rcd：记录最终结果 int mk[200][10],inrr[MAXV],rcd[MAXV]; // n：组数 // len：实际结点个数 int n,len; struct ENode { int adjvex; int weight; ENode *next; }; typedef struct VNode { int in; int data; ENode *firstE; }AdjList[MAXV]; typedef struct gAList { AdjList adjList; int numV,numE; }*GAList; void init() { len=0; mp.clear(); vec.clear(); vec.push_back("#"); // 为了从 1 开始，因为 mp 第二参数 int 默认为 0 mem(mk,0); mem(inrr,0); mem(rcd,0); } // 拓扑排序 int TopoSort(GAList GAL) { ENode *e; int top=0; int cnt=0; int *sk; sk=(int *)malloc((GAL->numV)*sizeof(int)); // 存入度为 0 的结点 for(int i=1;i<=GAL->numV;i++) // 因为从 1 开始，这里也得从 1 开始 if(GAL->adjList[i].in==0) sk[++top]=i; // ++top 从1开始，为下文 while(top!=0) 做准备 while(top!=0) { int gettop=sk[top--]; // 取出入度为 0 的结点 // printf("%d -> ",GAL->adjList[gettop].data); rcd[cnt++]=GAL->adjList[gettop].data; // 记录结果 for(e=GAL->adjList[gettop].firstE; e; e=e->next) { int k=e->adjvex; if(!(--GAL->adjList[k].in)) sk[++top]=k; } } if(cnt<GAL->numV) return 0; else return 1; } // 调试（可忽略） void showVec() { for(int i=1;i<=vec.size()-1;i++) { printf("%s ",vec[i].c_str()); } puts(""); } // 调试（可忽略） void showMP() { for(int i=1;i<=vec.size()-1;i++) { printf("mp[ %s ] == %d\n",vec[i].c_str(),mp[vec[i].c_str()]); } puts(""); } // 调试（可忽略） void showMK() { for(int i=1;i<=n;i++) { for(int j=1;j<=2;j++) { printf("%d ",mk[i][j]); } puts(""); } } int main() { int T; scanf("%d",&T); while(T-- && ~scanf("%d",&n)) { init(); int cnt=1,first=1; for(int i=1;i<=n;i++) { int j=1; string a,b; int x,y; cin>>a>>b; if(first) { first=0; vec.push_back(a); mp[a]=cnt; x=cnt++; vec.push_back(b); mp[b]=cnt; y=cnt++; } if(mp[a]==0) { vec.push_back(a); mp[a]=cnt; x=cnt++; } else x=mp[a]; if(mp[b]==0) { vec.push_back(b); mp[b]=cnt; y=cnt++; } else y=mp[b]; mk[i][j++]=x; // 1,1 开始 mk[i][j++]=y; inrr[y]++; // showVec(); // showMP(); } len=cnt-1; // 结点个数 // showMK(); // 创建 GAL GAList GAL=new gAList; GAL->numV=len; for(int i=1;i<=len;i++) { VNode &curV=GAL->adjList[i]; curV.data=i; curV.in=inrr[i]; curV.firstE=NULL; } for(int i=1;i<=n;i++) { VNode &curV=GAL->adjList[mk[i][1]]; ENode *e=new ENode; e->adjvex=mk[i][2]; e->next=curV.firstE; curV.firstE=e; } // 调试（可忽略） // for(int i=1;i<=len;i++) // { // VNode &curV=GAL->adjList[i]; // printf("adjList[%d]:\n",i); // printf("in == %d\n",curV.in); // printf("data == %d\n",curV.data); // printf("firstE == %d\n",curV.firstE); // puts(""); // } TopoSort(GAL); for(int i=0;i<len;i++) { if(i==0) printf("%s",vec[rcd[i]].c_str()); else printf(" %s",vec[rcd[i]].c_str()); } puts(""); } return 0; }
