牛客第五场 H subsequence 2 —— 拓扑排序

本文主要是介绍牛客第五场 H subsequence 2 —— 拓扑排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    长度为 $n$ 的字符串，以及 $m\cdot (m-1)/2$ 次说明
    每次说明给出两个字符，然后告诉这所有两个字符在原串中的相对位置
    最后还原该串

解题思路：

    易得，若有答案，只能为一种
    给出两个字符的所有位置，即可将任意两个字符的关系表示出来
    建完图后，拓扑排序的结果即为答案

核心：拓扑排序在串中的运用

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 1e4 + 5;
int n, m, in[26][maxn];
int cnt[26], num[26];
char s[maxn], two[2];
vector <pii> G[26][maxn];
vector <char> ans;void tp_sort(){queue <pii> Q;for(int i=0; i<26; i++)if(num[i] && in[i][0]==0)Q.push({i, 0});while(!Q.empty()){pii q = Q.front();Q.pop();ans.push_back(char(q.first + 'a'));for(auto i : G[q.first][q.second]){in[i.first][i.second]--;if(in[i.first][i.second]==0)Q.push(i);}}
}int main() {scanf("%d%d", &n, &m);for(int i=0; i<m*(m-1)/2; i++){int len, t0, t1;scanf("%s%d", two, &len);if(!len) continue;scanf("%s", s);memset(cnt, 0, sizeof(cnt));for(int j=0; j<len; j++){if(j){t1 = s[j] - 'a';G[t0][cnt[t0]-1].push_back({t1, cnt[t1]});in[t1][cnt[t1]]++;t0 = t1, cnt[t1]++;}else t0 = s[j] - 'a', cnt[t0]++;}num[two[0]-'a'] = cnt[two[0]-'a'];num[two[1]-'a'] = cnt[two[1]-'a'];}tp_sort();if(ans.size() != n) puts("-1");else for(auto i : ans) printf("%c", i);
}

这篇关于牛客第五场 H subsequence 2 —— 拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---