POJ - 1094 Sorting It All Out
题解：Floyd传递闭包
A<B A<C B<C C<D B<D A<B首先他给你这些关系，比如说：A<B,B<C我们很容易就能推出啊A<C，显然满足传递性，所以我们利用传递闭包求解，题目表示如果中途发现顺序混乱或者中途发现顺序确定，就可以不用管后面的输入了，但是如果从头到尾既没有发现顺序颠倒，也没有确定序列顺序，那么序列就是不能确定的。
1.所以我们需要对每次的输入都去进行传递闭包，观察有无顺序颠倒，我们来看一下什么叫做顺序颠倒
A B C D A 0 1 0 0 B 1 0 1 0 C 1 0 0 0 D 1 0 0 0很显然我们发现\(A<B并且B<A\),这说明：只要出现\(f[u][v] ==f[v][u]=1\)就能说明顺序有问题
2.那么什么样的情况顺序就确定了
A B C D
A 0 1 0 0
B 1 0 1 0
C 1 0 0 1
D 1 0 0 0这样的情况实际上已经确定了，即\((f[u][v]==1 || f[v][u]==1)并且 f[u][v]!=f[v][u]\)，如果所有的u和v在经过传递闭包后都满足此条件。说明顺序确定
3.顺序确定后如何输出序列
我们发现入度越大的节点他的位置就越靠后，所以我们根据\(f[u][v]\)矩阵中的v代表列，那么列中的1代表du[v]的入度，我们按照入度升序即可，最后按照顺序输出
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10;
int n, m;
int f[30][30];
int ff[30][30];
int du[30];
vector<pii> ans;
int floyd()
{
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
ff[i][j] = f[i][j];
for (int k = 1; k <= n; ++k)
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
{
if (u == v)
continue;
ff[u][v] |= ff[u][k] & ff[k][v];
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (i == j)
continue;
if (ff[i][j] && ff[j][i])
return -1; // 代表出现顺序异常
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (i == j)
continue;
if (!ff[i][j] && !ff[j][i])
return 0; // 代表还找不到顺序
}
}
return 1; // 代表已经找到顺序了
}
int main(void)
{
Zeoy;
int t = 1;
while (t--)
{
while (cin >> n >> m)
{
if (n == 0 && m == 0)
break;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
f[i][j] = 0, ff[i][j] = 0, du[i] = 0;
ans.clear();
int isprint = 0;
for (int i = 1; i <= m; ++i)
{
string s;
cin >> s;
s = " " + s;
int x = s[1] - 'A' + 1, y = s[3] - 'A' + 1;
f[x][y] = 1;
int ret = floyd();
// cout << "ret=" << ret << endl;
if (!isprint)
{
if (ret == -1)
{
cout << "Inconsistency found after " << i << " relations." << endl;
isprint = 1;
}
else if (ret == 1)
{
cout << "Sorted sequence determined after " << i << " relations: ";
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
if (ff[u][v])
du[v]++;
for (int i = 1; i <= n; ++i)
ans.push_back(make_pair(du[i], i));
sort(all(ans));
for (int i = 0; i < ans.size(); ++i)
cout << char(ans[i].second + 'A' - 1);
cout << ".\n";
isprint = 1;
}
}
}
if (!isprint)
cout << "Sorted sequence cannot be determined." << endl;
}
}
return 0;
}