题目链接
http://poj.org/problem?id=1094
题意
给出n个点，m对关系
判断 是否能够有一个确定的排列，或者矛盾，或者没有确定的排列
思路
在代码下面的注释中
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)); #define pb push_back #define bug puts("***bug***"); #define X first #define Y second #define L(on) (on<<1) #define R(on) (L(on) | 1) #define all(x) x.begin(), x.end() #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000"); #define syn_close ios::sync_with_stdio(false);cin.tie(0); //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 30 + 10; const int MOD = 1e9 + 7; int G[maxn][maxn]; int du[maxn]; int n, m; void Flyod() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) G[i][j] = (G[i][j] || (G[i][k] && G[k][j])); } bool judge() { for (int i = 1; i <= n; i++) if (G[i][i] == 1) return false; return true; } vector <int> ans; vector <int> g[maxn]; void toposort() { ans.clear(); queue <int> q; for (int i = 1; i <= n; i++) if (du[i] == 0) q.push(i); while (!q.empty()) { int id = q.front(); q.pop(); ans.pb(id); int len = g[id].size(); for (int i = 0; i < len; i++) if ((--du[g[id][i]]) == 0) q.push(g[id][i]); } } void print() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) printf("%d%c", G[i][j], j == n ? '\n' : ' '); } void clear() { for (int i = 1; i <= n; i++) { du[i] = G[i][i] = 0; g[i].clear(); for (int j = i + 1; j <= n; j++) G[i][j] = G[j][i] = 0; } } int main() { while (~scanf("%d%d", &n, &m) && (n || m)) { clear(); int x, y; int flag = 0; int vis = 0; char s[5]; for (int i = 0; i < m; i++) { scanf(" %s", s); x = s[0] - 'A' + 1; y = s[2] - 'A' + 1; if (vis == 0) { g[x].pb(y); du[y]++; } G[x][y] = 1; Flyod(); if (judge() == false && flag == 0 && vis == 0) flag = i + 1; else if (vis == 0) { int tot = 0; for (int j = 1; j <= n; j++) { int res = 0; for (int k = 1; k <= n; k++) res += G[j][k] || G[k][j]; if (res == n - 1) tot++; } if (tot == n) vis = i + 1; } } if (flag != 0) { printf("Inconsistency found after %d relations.\n", flag); continue; } if (vis == 0) { printf("Sorted sequence cannot be determined.\n"); continue; } toposort(); printf("Sorted sequence determined after %d relations: ", vis); for (int i = 0; i < n; i++) printf("%c", (ans[i] - 1 + 'A')); printf(".\n"); } } /* 如果 在当前给出的数据以上（包含当前这条数据） 已经能够确定答案 那么下面的数据是不用处理的 即使下面的数据会对答案造成影响 0.如何确定关系矛盾 我们用二分图 来构造一个有向图 G[i][j] 表示 i < j 然后用弗洛伊德跑一下 显然 如果给出的关系矛盾 一定是下面两种情况 0. A<A 1. A<B B<A 然后我们可以发现 如果用弗洛伊德跑一下 那么 A<B B<A 的关系 也会传递到 A<A B<B 也就是说 我们每次跑了弗洛伊德之后 判断一下 G[i][i] 之间是否有边 如果有 那么关系就已经矛盾了 那如何确定 顺序已经确定好了呢 有一种方法是 每次都拓扑排序一下 然后 每次队列里面只有一个入度为0的点 那么这次的拓扑排序就是确定的顺序了 还有一种方法是 判断一下 所有的点和其他的点之间是否都已经连了n - 1 条边了 如果是 那么顺序也是确定了的 （这里是无向边） 然后最后 如果既不矛盾，顺序又不确定 就是没法确定了 */转载于:https://www.cnblogs.com/Dup4/p/9433070.html
