P1347 排序 (拓扑排序)
程序员文章站
2022-03-20 13:06:20
题目 "P1347 排序" 解析 打开一看拓扑排序,要判环。 三种情况 有环(存在矛盾) 没环但在拓扑排序时存在有两个及以上的点入度为0(关系无法确定) 除了上两种情况(关系可确定) 本来懒了一下,直接在排序时判环,然后一直WA,遂怒写tarjan判环,第一个点注意特判两个点相同的情况,注意重边。 ......
题目
解析
打开一看拓扑排序,要判环。
三种情况
- 有环(存在矛盾)
- 没环但在拓扑排序时存在有两个及以上的点入度为0(关系无法确定)
- 除了上两种情况(关系可确定)
本来懒了一下,直接在排序时判环,然后一直wa,遂怒写tarjan判环,第一个点注意特判两个点相同的情况,注意重边。
然后就有了这又臭又长的
代码
#include <bits/stdc++.h> using namespace std; const int n = 1000; int n, m, num, sum, tot; int du[n], head[n], in[n], ans[n], dfn[n], low[n], size[n]; bool vis[n]; char s[n]; queue<int>q; struct node { int v, nx; } e[n]; template<class t>inline void read(t &x) { x = 0; int f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); x = f ? -x : x ; return; } inline void add(int u, int v) { for (int i = head[u]; ~i; i = e[i].nx) if (e[i].v == v) return; e[++num].nx = head[u], e[num].v = v, head[u] = num, in[v]++; } int topo() { int tmp = 0, cnt = 0; for (int i = 1; i <= n; ++i) if (!du[i]) q.push(i), tmp++; if (tmp > 1) return 0; while (!q.empty()) { tmp = 0, cnt++; int u = q.front(); q.pop(); ans[cnt] = u; for (int i = head[u]; ~i; i = e[i].nx) { int v = e[i].v; du[v]--; if (!du[v]) q.push(v), tmp++; } if (tmp > 1) return 0; } return 1; } stack<int>sta; void tarjan(int u) { dfn[u] = low[u] = ++tot; vis[u] = 1; sta.push(u); for (int i = head[u]; ~i; i = e[i].nx) { int v = e[i].v; if (!dfn[v]) tarjan(v), low[u] = min(low[u], dfn[u]); else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { int x = -1; sum++; while (x != u) { x = sta.top(), sta.pop(); vis[u] = 0, size[sum]++; } } } int main() { memset(head, -1, sizeof head); read(n), read(m); for (int i = 1; i <= m; ++i) { scanf("%s", s); add(s[0] - 'a' + 1, s[2] - 'a' + 1); if(s[0] == s[2]) { printf("inconsistency found after %d relations.", i); return 0; } sum = tot = 0; memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low); memset(vis, 0, sizeof vis); memset(size, 0, sizeof size); for (int j = 1; j <= n; ++j) if (!dfn[j]) tarjan(j); for (int j = 1; j <= sum; ++j) if (size[j] > 1) { printf("inconsistency found after %d relations.", i); return 0; } memcpy(du, in, sizeof du); while (!q.empty()) q.pop(); int k = topo(); if (k == 1) { printf("sorted sequence determined after %d relations: ", i); for (int j = 1; j <= n; ++j) printf("%c", ans[j] + 'a' - 1); printf("."); return 0; } else continue; } printf("sorted sequence cannot be determined."); return 0; }
上一篇: Java运行时数据区域
下一篇: Java面向对象三大特性