526互联

subsequence 2 (拓扑排序)

发布时间 2023-05-24 09:50:07作者: VxiaohuanV

题面大意:

给定一个隐藏字符串, 每次给出2个字母所产生的子序列, 问你原序列是什么

 思路:

  • 性质: 字母和字母之间有先后顺序
  • 因此拓扑排序建边来做
  • 然后不要一次把边建完, 而是通过相对位置关系, 边更新,边建. (先找第一个,在找第二个....)
#include<bits/stdc++.h>
 
using namespace std;
 
const int N=1e4+10;
vector<int> vec[N*30];
int indeg[N*30],num[30];
 
int main()
{
    int n,m;
    cin>>n>>m;
    int ncase=m*(m-1)/2;
 
    while(ncase--)
    {
        string op,t;
        int len;
        cin>>op>>len;
 
        if(!len){
            getchar();continue;
        }
 
        cin>>t;
        ///给提示字符串中的字符建边
        int a=0,b=0,cur=0,id=0;
        for(int i=0;i<len;i++)
        {
            if(t[i]==op[0]){
                a++;
                id=(t[i]-'a')*10000+a;
            }
            else{
                b++;
                id=(t[i]-'a')*10000+b;
            }
            if(cur){
                indeg[id]++;
                vec[cur].push_back(id);
            }
            cur=id;
        }
        num[op[0]-'a']=a;
        num[op[1]-'a']=b;
    }
    
    ///存放入度为0的点
    queue<int> que;
 
    for(int i=0;i<26;i++){
        if(num[i]&&indeg[i*10000+1]==0)
            que.push(i*10000+1);
    }
 
    string ans;
 
    while(!que.empty()){
 
        int top=que.front();
        que.pop();
        ans+=(char)((top-1)/10000+'a');
        for(auto v: vec[top]){
            indeg[v]--;
            if(!indeg[v]){
                que.push(v);
            }
        }
    }
 
    if(ans.size()!=n){
        printf("-1\n");
    }
    else cout<<ans<<endl;
    return 0;
}
随便偷的代码