拓扑排序
在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。
拓扑排序最经典的算法是Kahn算法。
// deg是入度,在存图的时候需要录入数据
// A是排序后的数组
// n是点的数量
int deg[MAXN], A[MAXN];
bool toposort(int n)
{
int cnt = 0;
queue<int> q;
for (int i = 1; i <= n; ++i)
if (deg[i] == 0)
q.push(i);
while (!q.empty())
{
int t = q.front();
q.pop();
A[cnt++] = t;
for (auto to : edges[t])
{
deg[to]--;
if (deg[to] == 0) // 出现了新的入度为0的点
q.push(to);
}
}
return cnt == n;
}
有一道例题:CF510C Fox And Names
#include<bits/stdc++.h>
//#define LOCAL
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
string lexicographic = "abcdefghijklmnopqrstuvwxyz";
int dist[MAXN], pre[MAXN];
int head[MAXN];
set<int> vertex;
int deg[MAXN], A[MAXN];
int cnt = 1;
int n, m;
struct Edge {
int from, to, w, next;
} edges[MAXN];
void add(int u, int v, int w) {//添加一条边u--v
edges[cnt].to = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
bool update(string s1, string s2) {
auto minlen = min(s1.size(), s2.size());
for (int i = 0; i < minlen; ++i) {
if (s1[i] != s2[i]) {
add(s1[i], s2[i], 0);
vertex.insert(s1[i]);
vertex.insert(s2[i]);
deg[s2[i]]++;
return true;
}
}
if (s1.size() > s2.size())return false;
return true;
}
bool toposort() {
int cntt = 0;
priority_queue<int, vector<int>, greater<>> q;
for (auto v: vertex) {
if (deg[v] == 0)
q.push(v);
}
while (!q.empty()) {
int t = q.top();
q.pop();
A[cntt++] = t;
for (int i = head[t]; i != -1; i = edges[i].next) {
int to = edges[i].to, w1 = edges[i].w;
deg[to]--;
if (deg[to] == 0)
q.push(to);
}
}
return cntt == vertex.size();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
memset(head, -1, sizeof(head));
cin >> n;
string name1, name2;
if (n == 1) {
print(lexicographic);
exit(0);
}
cin >> name1;
for (int i = 1; i < n; ++i) {
cin >> name2;
if (!update(name1, name2)) {
print("Impossible");
exit(0);
}
name1 = name2;
}
if (toposort()) {
for (int i = 0; i < vertex.size(); ++i) {
cout << (char) A[i];
}
} else {
print("Impossible");
exit(0);
}
for (auto ch: lexicographic) {
if (find(A, A + vertex.size(), ch) == A + vertex.size())cout << (char) ch;
}
}
最后更新于