【CodeForeces】【#290_(div.2)_C】拓扑排序

本文主要是介绍【CodeForeces】【#290_(div.2)_C】拓扑排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出n个单词，已知单词们已经按“字典序”递增排好。问题是，这个“字典序”并不是传统的abc，而是26个字母的未知排列。你需要做的是求出这个排列。当然有一些重复的特殊情况之类的，就不多说了。

思路：

拓扑排序，将26个字母视作26个点，根据给出的单词表，可以从中处理出一些数据，即“某字母a小于某字母b”，然后就在a到b建一条边。建好图之后拓扑排序得到答案。

遗憾的是，题目有cheat。

比如：

2

aaa

aa

唉。没想到。 特判咯~

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;char str[120][120];
int n;
int grid[26][26];
int ru[26],vis[26];
char ans[30];
int cheat;void cmp(int a,int b){int lena = strlen(str[a]);int lenb = strlen(str[b]);int len = min(lena,lenb);for(int i=0;i<len;i++){if(str[a][i] != str[b][i]){int from = str[a][i] - 'a';int to = str[b][i] - 'a';grid[from][to] = 1;return;}}if(lena > lenb) cheat=1;
}void topoSort(){int i,j,t=0; ///初始化入度数组for(i=0;i<26;i++){for(j=0;j<26;j++){if(i!=j && grid[i][j]){ru[j]++;}}}while(1){int found=0;for(i=0;i<26;i++){if(!vis[i] && ru[i] == 0){found = 1;char ch = i + 'a';ans[t++] = ch;for(j=0;j<26;j++){if(grid[i][j]){ru[j]--;}}vis[i] = 1;break;}}if(!found)break;}if(strlen(ans)!=26) cout<<"Impossible"<<endl;else printf("%s\n",ans);
}int main()
{memset(grid,0,sizeof(grid));memset(ru,0,sizeof(ru));memset(vis,0,sizeof(vis));cin>>n;int i,j;for(i=0;i<n;i++){scanf("%s",str[i]);}for(i=0;i<n;i++){for(j=i+1;j<n;j++){cheat = 0;cmp(i,j);if(cheat){cout<<"Impossible"<<endl;return 0;}}}topoSort();return 0;
}

这篇关于【CodeForeces】【#290_(div.2)_C】拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---