题意：给你一个字符串的长度n 现在询问了m*（m-1）/2次 每次都可以询问两个字符 然后 会告诉你只留下这两个字符后 字符串的样子 现在问你能不能还原字符串 如果能就输出字符串 否则输出-1
思路：我们可以发现每次返回的字符串都有明显的拓扑关系 所以我们每次都进行前后连边 然后就是对于同一个字符 我们需要进行编号 最后还有一些细节判断
#include <bits/stdc++.h> using namespace std; const int N = 3e5+7; const int inf = 0x3f3f3f3f; typedef long long ll; const ll mod = 1e7+9; int n,m; int num[30],ru[N],vis[N]; vector<int> G[N]; int no=1e4; vector<char> s; bool top(){ queue<int> q; int gg=0; int xx=0; for(int i=0;i<m;i++){ gg+=num[i]; if(!num[i]) xx++; for(int j=1;j<=num[i];j++) if(!ru[j+i*no]&&!vis[j+i*no]){ q.push(j+i*no); vis[j+i*no]=1; } } int res=0; while(!q.empty()){ int tmp=q.front(); q.pop(); res++; s.push_back(char(tmp/no+'a')); for(int i=0;i<G[tmp].size();i++){ ru[G[tmp][i]]--; if(!ru[G[tmp][i]]&&!vis[G[tmp][i]]){ q.push(G[tmp][i]); vis[G[tmp][i]]=1; } } } if(gg!=res) return false; int len=s.size(); if(len==n) return true; else if(len<n){ if(len+xx<=n){ for(int i=0;i<m;i++) if(!num[i]) s.push_back(char(i+'a')); len=len+xx; while(len<n){ s.push_back(char('a')); len++; } }else{ return false; } }else return false; } int main(){ //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=m*(m-1)/2;i++){ char a,b; cin>>a>>b; int len; cin>>len; getchar(); string s; getline(cin,s); if(!num[a-'a']) for(int j=0;j<len;j++) if(s[j]==a) num[a-'a']++; if(!num[b-'a']) for(int j=0;j<len;j++) if(s[j]==b) num[b-'a']++; int cnt[20]={0}; for(int j=0;j<len-1;j++){ int x,y; if(j==0) cnt[s[j]-'a']++; x=cnt[s[j]-'a']; cnt[s[j+1]-'a']++; y=cnt[s[j+1]-'a']; G[x+(s[j]-'a')*no].push_back(y+(s[j+1]-'a')*no); ru[y+(s[j+1]-'a')*no]++; } } if(top()){ for(int i=0;i<s.size();i++) cout<<s[i]; cout<<endl; }else{ cout<<"-1"<<endl; } }