病毒virus（拓扑排序）

解题思路:单词依字典序排列， 因此可以判断单词中字符是否存在拓扑序， 如果存在， 则遍历病毒字符串中的字符， 如果每一个字符都存在映射的索引， 则依照索引0 为‘a’ 依次输出， 否则输出0；

注意事项:在比较字典单词的字符时， 注意判断是否越界； 进行拓扑排序时，判断是否具有拓扑序

参考代码:

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
stack<int> stk;
int g[30][30];
int ind[30],v[30],map[30]; //ind[] 入度， v[]是否应该入栈，map[]字符映射
string s[N],ans,str,res;// s[] 输入的感染字典， str 输入的感染字符串，res感染字符拓扑排序
//构建图
void build_graph(int n){
    for(int i = 1; i <= n; i ++){
        int j = 0;
        while(s[i][j] == s[i+1][j] && j < s[i].size() && j < s[i + 1].size()){
            j ++;
        }
        if(j == s[i].size() || j == s[i+1].size()) continue;
        g[s[i][j] - 'a'][s[i + 1][ j] - 'a' ] = 1;
        ind[s[i + 1][j] - 'a'] += 1;
        v[s[i][j] - 'a'] = 1;
        v[s[i + 1][j] - 'a'] = 1;
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> s[i];     
    }
    //构建图
    build_graph(n);
    cin >> str;
    //拓扑排序
    for(int i = 0; i <30; i ++){
        if(!ind[i] && v[i] == 1){
            stk.push(i);
            v[i] = 0;
        }
    }
    while(!stk.empty()){
            int c = stk.top();
            stk.pop();
            res += char(c + 'a');
            for(int i = 0; i < 30; i ++){
                if(g[c][i]) ind[i] --;
                if(ind[i] == 0  && v[i]) {
                    stk.push(i);
                    v[i] = 0;
                }
            }
    }
    //如果res为空， 则不存在拓扑排序， 输出结果0
    if(res.empty()){
        cout << 0;
        return 0;
    }
    memset(map, -1, sizeof(map));
    //建立感染字符与索引的映射
    for(int i = 0; i < res.size(); i ++){
        map[res[i]] = i;
    }
    for(int i = 0; i < str.size(); i ++){    
        if(map[str[i]]== -1){
            cout << 0;
            return 0;
        }
        //从a开始按照索引位置拼接字符串
        ans += char(map[str[i]] + 'a');
    }
    cout << ans <<endl;
    return 0;
}