1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n, m; int u[605], v[605]; // 通过前 x 条关系,能否确定顺序 // 0:无法确定,1:可以确定,2:存在矛盾 int d[30]; queue<int> q; vector<int> e[30]; string s; int check(int x) { // 清空所有东西 for (int i = 1; i <= n; i++) { d[i] = 0; e[i].clear(); } while (!q.empty()) q.pop(); s = ""; // 前 x 条边加入图 for (int i = 1; i <= x; i++) { e[u[i]].push_back(v[i]); d[v[i]]++; } // 拓扑排序 bool flag = false; // 多解标记 // 1. 所有入度为 0 的点作为起点 for (int i = 1; i <= n; i++) if (d[i] == 0) q.push(i); // 2. 类似与广搜的扩展 while (!q.empty()) { // 有多解 if (q.size() > 1) flag = true; // 正常扩展 int now = q.front(); q.pop(); // 记录答案 s = s + (char)(now - 1 + 'A'); for (int i = 0; i < e[now].size(); i++) { int nxt = e[now][i]; d[nxt]--; if (d[nxt] == 0) q.push(nxt); } } if (s.size() != n) return 2; // 存在矛盾 if (flag) return 0; // 无法确定 // 没有多解和矛盾的时候,你当前的解才是唯一解 return 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { string s; cin >> s; if (s[1] == '<') u[i] = s[0] - 'A' + 1, v[i] = s[2] - 'A' + 1; else v[i] = s[0] - 'A' + 1, u[i] = s[2] - 'A' + 1; } for (int i = 1; i <= m; i++) { int res = check(i); if (res == 1) { cout << "Sorted sequence determined after " << i << " relations: " << s << "."; return 0; } if (res == 2) { cout << "Inconsistency found after " << i << " relations."; return 0; } } cout << "Sorted sequence cannot be determined."; return 0; }
信息
- ID
- 2156
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 8
- 已通过
- 4
- 上传者