P1347 排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列
A
,
B
,
C
,
D
A,B,C,D
A,B,C,D 表示
A
<
B
,
B
<
C
,
C
<
D
A<B,B<C,C<D
A<B,B<C,C<D。在这道题中，我们将给你一系列形如
A
<
B
A<B
A<B 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入格式
第一行有两个正整数
n
,
m
n,m
n,m，
n
n
n 表示需要排序的元素数量，
2
≤
n
≤
26
2\\leq n\\leq 26
2≤n≤26，第
1
1
1 到
n
n
n 个元素将用大写的
A
,
B
,
C
,
D
,
…
A,B,C,D,\\dots
A,B,C,D,… 表示。
m
m
m 表示将给出的形如
A
<
B
A<B
A<B 的关系的数量。
接下来有
m
m
m 行，每行有
3
3
3 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。
输出格式
若根据前
x
x
x 个关系即可确定这
n
n
n 个元素的顺序 yyy..y（如 ABC），输出
Sorted sequence determined after x relations: yyy…y.
其中
x
x
x 表示上述的前
x
x
x 个关系。
若根据前
x
x
x 个关系即发现存在矛盾（如
A
<
B
,
B
<
C
,
C
<
A
A<B,B<C,C<A
A<B,B<C,C<A），输出
Inconsistency found after x relations.
其中
x
x
x 表示的意义同上。
若根据这
m
m
m 个关系无法确定这
n
n
n 个元素的顺序，输出
Sorted sequence cannot be determined.
（提示：确定
n
n
n 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）
输入输出样例 #1
输入 #1
4 6
A<B
A<C
B<C
C<D
B<D
A<B
输出 #1
Sorted sequence determined after 4 relations: ABCD.
输入输出样例 #2
输入 #2
3 2
A<B
B<A
输出 #2
Inconsistency found after 2 relations.
输入输出样例 #3
输入 #3
26 1
A<Z
输出 #3
Sorted sequence cannot be determined.
说明/提示
2
≤
n
≤
26
,
1
≤
m
≤
600
2 \\leq n \\leq 26,1 \\leq m \\leq 600
2≤n≤26,1≤m≤600。
解析
// 有向图无环, 且连通
// 我这里想表达一下我的情绪, 这题我千算万算没想到我居然是错在输出没写换行符, 我非常生气😡
#include<iostream>
#include<cstdio>
#include<vector>
#include<unordered_map>
#include<queue>
#include<unordered_set>
using namespace std;
struct Edge {
char toNode;
int nextEdge;
};
struct PairHash {
size_t operator()(const pair<char, char> &p) const {
return hash<char>()(p.first) * 31 + hash<char>()(p.second);
}
};
int n, m;
char a, b;
unordered_map<char, int> head;
vector<Edge> edges;
int cnt = 1;
bool isLoop, isSuccess;
unordered_map<char, int> color; // 标记结点颜色
unordered_map<pair<char, char>, int, PairHash> estalished;
unordered_map<char, int> indegree; // 结点入度
unordered_set<char> node; // 记录当前结点
void addEdge(char u, char v) {
edges[cnt] = {v, head[u]};
head[u] = cnt++;
}
void init(char u, char v) {
if (color.find(u) == color.end()) color[u] = 0;
if (color.find(v) == color.end()) color[v] = 0;
}
// 利用topo算法判断是否有环
void dfs(char id) {
if (isLoop) return; // 直接返回
color[id] = 1;
for (int i = head[id]; i; i = edges[i].nextEdge) {
char toNode = edges[i].toNode;
if (color[toNode] == 0) dfs(toNode);
else{
isLoop = true;
return;
}
}
}
// 利用kahn算法求topo序列层数
bool kahn(vector<char> &topo, unordered_map<char, int> ind) {
topo.clear();
// 将入度为0的结点入队
queue<char> q;
unordered_map<char, int> level; // 记录每个结点的层数
int res = 0;
for (const auto e : node) {
if (ind[e] == 0) q.push(e), level[e] = 1;
}
char e;
while (!q.empty()) {
e = q.front(), q.pop();
topo.push_back(e);
for (int i = head[e]; i; i = edges[i].nextEdge) {
char toNode = edges[i].toNode;
level[toNode] = max(level[toNode], level[e] + 1);
res = max(res, level[toNode]);
if (—ind[toNode] == 0)
q.push(toNode);
}
}
return res == n;
}
int main() {
scanf("%d %d", &n, &m);
edges.resize(m + 1);
for (int i = 0; i < m; i++) {
scanf(" %c<%c", &a, &b);
// 建立a–>b
if (!estalished[{a, b}]) {
addEdge(a, b);
estalished[{a, b}] = 1;
indegree[b]++;
node.insert(a);
node.insert(b);
}
vector<char> topo;
isSuccess = kahn(topo, indegree);
// 判断是否有环
if (topo.size() < node.size()) {
printf("Inconsistency found after %d relations.\\n", i + 1);
isLoop = true;
break;
}
// 判断是否能够决定关系
if (isSuccess) {
printf("Sorted sequence determined after %d relations: ", i + 1);
for (const auto e : topo) printf("%c", e);
printf(".\\n");
break;
}
}
if (!isSuccess && !isLoop) {
printf("Sorted sequence cannot be determined.\\n");
}
return 0;
}
