信息学奥赛一本通T1396：病毒

【题目描述】

有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。

现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。

现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。

【输入】

第一行为整数K（≤50000），表示字典中的单词个数。

以下K行，是被病毒感染了的字典，每行一个单词。

最后一行是需要你恢复的一串字母。

所有字母均为小写。

【输出】

输出仅一行，为恢复后的一串字母。当然也有可能出现字典不完整、甚至字典是错的情况，这时请输出一个0。

【输入样例】

6
cebdbac
cac
ecd
dca
aba
bac
cedab

【输出样例】

abcde

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 50001
#define MOD 123
#define E 1e-6
using namespace std;
int n;
int a[N][101],g[27][27];
int enter[27],vis[27],sum[27];
int cnt;
int p;
void judge(int x,int y)
{
    if(a[x][y]==0||a[x+1][y]==0)
        return ;
    if(a[x][y]!=a[x+1][y])
    {
        g[a[x][y]][a[x+1][y]]=1;
        enter[a[x+1][y]]++;
    }
    else
        judge(x,y+1);
}
bool topsort()
{
    for(int i=1;i<=27;++i)
        if(vis[i])
            cnt++;
    for(int i=1;i<n;++i)
        judge(i,1);

    int work,temp;
    while(p!=cnt)
    {
        work=0;
        for(int i=1;i<=cnt;++i)
        {
            if(enter[i]==0)
            {
                temp=i;
                enter[i]=-1;
                work++;
            }
        }
        if(work!=1)
            return false;
        sum[++p]=temp;
        for(int i=1;i<=cnt;++i)
        {
            if(g[temp][i])
            {
                g[temp][i]=0;
                enter[i]--;
            }
        }
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=1;i<=(n+1);i++)
    {
        string str;
        cin>>str;
        for(int j=0;j<str.size();j++)
        {
            a[i][++a[i][0]]=int(str[j]+1-'a');
            vis[str[j]+1-'a']=1;
        }
    }

    if(!topsort())
        cout<<0;
    else
    {
        for(int i=1;i<=a[n+1][0];++i)
        {
            for(int j=1;j<=cnt;++j)
            {
                if(a[n+1][i]==sum[j])
                {
                    cout<<char(j-1+'a');
                    break;
                }
            }
        }
    }
    return 0;
}

信息学奥赛一本通T1396：拓扑排序与关键路径 病毒 归属于 拓扑排序与关键路径，更多同类题解源程序见：拓扑排序与关键路径 和 病毒