首页 > 代码库 > 【拓扑排序】CDOJ1635 琵琶弦上说相思，当时明月在，曾照彩云归
【拓扑排序】CDOJ1635 琵琶弦上说相思，当时明月在，曾照彩云归
对于两个相邻的字符串 Si和Si+1 ，如果它们的前k-1位都相同，第k位不相同，那么，在字典序中 Si,k一定在 Si+1,k前面
建立有向边从 Si,k到 Si+1,k，进行拓扑排序
为了保证字典序最小，需要用堆维护拓扑过程。
技巧是讲空白也放到字典序里，一起拓扑。并且空白的字典序如果不是最小的话，一定无解。
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int first[1010],__next[210*1010],v[210*1010],e;
void AddEdge(int U,int V){
v[++e]=V;
__next[e]=first[U];
first[U]=e;
}
char a[1010][210],anss[101];
int n,len[1010],ru[1010],ans;
bool vis[1010];
priority_queue<int,vector<int>,greater<int> >Heap;
int main(){
// freopen("d.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",a[i]+1);
len[i]=strlen(a[i]+1);
}
for(int i=1;i<=200;++i){
for(int j=1;j<n;++j){
if(!vis[j]){
if(a[j][i]!=a[j+1][i]){
vis[j]=1;
AddEdge(a[j][i],a[j+1][i]);
++ru[a[j+1][i]];
}
}
}
}
for(int i=‘a‘;i<=‘z‘;++i){
if(!ru[i]){
Heap.push(i);
}
}
if(!ru[0]){
Heap.push(0);
}
while(!Heap.empty()){
int U=Heap.top(); Heap.pop();
anss[++ans]=U;
for(int i=first[U];i;i=__next[i]){
--ru[v[i]];
if(!ru[v[i]]){
Heap.push(v[i]);
}
}
}
anss[ans+1]=‘\0‘;
puts((ans==27 && anss[1]==0) ? anss+2 : "-1");
return 0;
}
【拓扑排序】CDOJ1635 琵琶弦上说相思，当时明月在，曾照彩云归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。