题目大意
给m*（m-1）/2行信息，包含两个字母和一行字符串，表示在一个未知字符串中的两个字母的前后位置关系，如原字符串为abcab，两个字母为ab,那么得到的字符串就是abab。
原字符串长度为n，如果能根据信息构造出这样的字符串，输出一种情况，如果不能输出-1。
n<=1e4,m<=10
思路
我们知道所给的信息表示的是某一种字符在原字符串中与另一种字符串的位置关系和数量。可以看作一种单向边，如aabb，我们就可以把两个b放在两个a的后边。用拓扑排序，就可以把有向图表示成先后关系和数量关系不变的序列。而要构造这样的边，我们只要在输入时给每种字符编号即可，用编号建边，用编号输出即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ls 2*x
#define rs 2*x+1
#define mid ((l+r)/2)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
const int N=1e3+10;
const int mod=1e9+7;
const int inf=1e18;
int in[N],num[N],p[N],vis[N],pos[N][N];
char a[N];
vector<int> g[N];
queue<int> q;
signed main() {
IOS
int n, m, cnt = 0;
cin>>n>>m;
m=m*(m-1)/2;
for(int j = 1; j <= m; ++j) {
string s1,s2;
int len;
cin>>s1>>len;
if(len>0)cin>>s2;
for(int i=0;i<s2.size();++i) {
int x=s2[i]-'a';
if(!vis[x]){
a[++cnt]=s2[i];
pos[x][num[x]++] = cnt;
p[i]=cnt;
} else
p[i]=pos[x][num[x]++];
}
for(int i = 1; i < s2.size(); ++i) {
g[p[i-1]].push_back(p[i]);
in[p[i]]++;
}
vis[s1[0]-'a']=vis[s1[1]-'a']=1;
num[s1[0]-'a']=num[s1[1]-'a']=0;
}
for(int i = 1; i <= cnt; ++i)
if(in[i] == 0) q.push(i);
string ans;
while(!q.empty()) {
int tmp = q.front();
q.pop();
ans+=a[tmp];
for(int i=0;i<g[tmp].size();++i) {
int v=g[tmp][i];
in[v]--;
if(in[v] == 0)q.push(v);
}
}
if(ans.size() == n)
cout << ans << endl;
else
cout << "-1" << endl;
return 0;
}
|