题目链接
1.有唯一拓扑序
2.存在多个拓扑序
3.有环（不存在拓扑序）
解法一：拓扑排序
时间复杂度\(O(M*(N+M))\)
题意
每次给定我们一个条件：\(X<Y\)
让我们判断何时能把所有数之间的关系明确的找出来
- 如果找出来了，提前结束，即后面即使出现了矛盾也不管了
- 如果出现了矛盾，提前结束
- 既不出现矛盾也找不出所有数之间的关系
思路
把\(A\)<\(B\)看做由\(A\)指向\(B\)的一条边
每次加入一条边就做一次拓扑排序，此时会有两种情况：
- 所有边都加入了拓扑队列当中
- 有至少一条边没有加入队列当中
对于情况2，显然是出现了环，有环就说明出现了冲突(\(A<B\) && \(B<A\))
对于情况1，还有两种情况： - 每个时刻中队列都只有一个数
- 有至少一个时刻队列中存在至少两个数。这是一个坑点,想了一个多小时。我们下面详细解释。
先举个例子：
- 对于\(A<B\),\(A<C\),这两个条件，我们是无法得出\(A,B,C\)之间的关系的，准确的来说是无法确定\(B\)和\(C\)之间的关系
- 对于\(A<B\), \(B<C\), \(D<E\)这三个条件，我们可以确定\(A,B,C\)之间的关系和\(D,E\)之间的关系，但是我们无法确定 \(A,B,C\)与\(D,E\)之间的关系
但是，上述两个例子都是有拓扑序的。并且，都存在至少一个时刻，队列至少存在两个元素。 - 当\(A\)出队时，\(B,C\)入队，队列中存在两个元素
- 初始状态时,\(A,D\)的入度为0，此时队列中存在两个元素
我们可以发现，只要某一时间队列中存在多余一个元素，就说明存在\(A<B\)和\(A<C\)的情况，对于情况2我们可以看做一个虚拟源点\(V\)同时\(<A\)和\(<D\)
总上，也就是说没两个点之间的关系必须唯一确定。
可以用 top_sort 判断以下三种情况：
- 有唯一拓扑序
- 存在多个拓扑序
- 有环（不存在拓扑序）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 30, M = 10100;
int n, m;
int h[N], e[M], ne[M], idx;
int deg[N], din[N];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort(bool &flag)
{
int hh = 0, tt = -1;
for(int i = 0; i < n; i ++ ) din[i] = deg[i];
for(int i = 0; i < n; i ++ )
if(!din[i])
q[ ++ tt ] = i;
while(hh <= tt)
{
if(tt - hh >= 1) flag = false;//不可以放在while循环的外面
int t = q[hh ++ ];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(-- din[j] == 0) q[ ++ tt ] = j;
}
}
return tt == n - 1;
}
void init()
{
memset(h, -1, sizeof h);
idx = 0;
memset(din, 0, sizeof din);
memset(deg, 0, sizeof deg);
}
int main()
{
while(cin >> n >> m, n || m)
{
init();
bool is_done = false;
for(int i = 1; i <= m; i ++ )
{
string s; cin >> s;
int a = s[0] - 'A', b = s[2] - 'A';
add(a, b);
deg[b] ++ ;
if(is_done) continue;//已经有结果或者结果矛盾了
bool is_one_root = true;
bool has_res = topsort(is_one_root);
if(!has_res)//出现矛盾
{
printf("Inconsistency found after %d relations.\n",i);
is_done = true;
}
else if(has_res && is_one_root)
{
printf("Sorted sequence determined after %d relations: ",i);
for(int i = 0; i < n; i ++ ) cout << char(q[i] + 'A');
puts(".");
is_done = true;
}
}
if(!is_done) puts("Sorted sequence cannot be determined.");
}
return 0;
}
解法二：Floyd算法
时间复杂度：\(O(N^3)\)
思路：
每加入一条边就用这条边对所有边做一次传递递包操作
然后判断是否存在自环，有自环就说明同时存在\(A<B\)，\(B<A\)
传递递包：
已知：\(A<B\)，\(B<\)C 则：\(A<C\)
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int N = 26;
int n, m, t, d[N][N], g[N][N], in[N]; //有无向边就代表关系出错 若一个点能够到达其他所有边那么排序完成 执行一次拓扑序即可
char s[4];
void floyd() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//i-->k有边 且 k-->j有边 那么i-->j有边
if (g[i][k] && g[k][j]) g[i][j] = 1;
}
}
}
}
void topsort() {
queue<int> q;
for (int i = 0; i < n; i++) if (!in[i]) q.push(i);
printf("Sorted sequence determined after %d relations: ", t);
while (!q.empty()) {
int u = q.front();
q.pop();
printf("%c", (char)('A' + u));
for (int v = 0; v < n; v++) {
if (d[u][v]) { //查找的时候我们应按照非闭包图来求
in[v]--;
if (!in[v]) q.push(v);
}
}
}
printf(".\n");
}
int main() {
while (scanf("%d%d", &n, &m), n) {
memset(g, 0, sizeof(g)); //0代表没有边 1代表有边 、
memset(d, 0, sizeof(d));
memset(in, 0, sizeof(in));
bool find = false, fail = false; //若为true代表找到一种序列
for (int j = 1; j <= m; j++) {
scanf("%s", s);
if (find || fail) continue; //就不用继续查找了
int u = s[0] - 'A'; //A < B 那么建立一条A->B的边 若出现双向边代表出错
int v = s[2] - 'A';
in[v]++;//入度增加
g[u][v] = d[u][v] = 1; //求一次floyd
floyd();
//检查一下
find = true; //假定找到了
for (int u = 0; u < n; u++) {
if (g[u][u]) { //代表出现了 A < A
fail = true; //存在双向边 状态出错了
break;
}
for (int v = 0; v < n; v++) {
//必须满足 其中一个为0 一个为1 若2个都为0 0 或 1 1则不合法
if (u != v && (!g[u][v] && !g[v][u])) find = false;//代表有一条边不连通
}
}
t = j;
}
if (fail) printf("Inconsistency found after %d relations.\n", t);
else if (find) topsort();
else printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
2024/3/9
思路：对于任意合法序列例如\(A<B<C<D(n=4)\)
\(A\) 的后面有 \(3\) 个比它大的，\(B\) 的后面有 \(2\) 个比它大的
\(C\) 的后面有 \(1\) 个比它大的，\(D\) 的后面没有比它大的
因此我们可以设置一个数组 \(st[i]\) 用来表示是否存在一点它满足有 \(i\) 个比它大的数
如果存在这么一个合法序列，那么 \(st[0,1,...,n-1]\) 必定都存在
两个坑：
- 不可以提前 \(break\) 掉输入，因为有多组数据，如果你提前 \(break\) 掉当前这一组数据的输入，那么该组数据的后续输入会影响下一组数据
- \(st\) 应该放在 \(check\) 里面初始化而不是读入一次新数据时初始化，因为可能存在同一点，它在不同时刻满足 \(st[0]=true\), \(st[1]=true\) ....，而我们希望的是每个满足 \(st[]=true\) 的点都互不相同
其实这样做和通过 \(top_sort\) 来判断本质上是一样的，因为如果满足我们想要的 \(st[0,1,...,n-1]=true\)，其实就是满足存在一个唯一的拓扑序。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
int n, m;
bool g[N][N]; // g[l][r] --> l < r
bool st[N]; // st[i]=true --> 存在某个数有i个比它大的数
char ch[N];
bool check()
{
memset(st, false, sizeof st); // // WRONG 3
for(int i = 1; i <= n; i ++ )
{
int sum = 0;
for(int j = 1; j <= n; j ++ ) sum += g[i][j];
st[sum] = true;
ch[sum] = 'A' + i - 1;
}
int cnt = 0;
for(int i = 0; i < n; i ++ ) cnt += st[i];
return cnt == n;
}
void floyd()
{
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
for(int k = 1; k <= n; k ++ )
g[i][j] |= g[i][k] & g[k][j];
}
int main()
{
while(cin >> n >> m, n || m)
{
// memset(st, false, sizeof st); // WRONG 1
memset(g, false, sizeof g);
bool flag = false;
for(int i = 1; i <= m; i ++ )
{
string s; cin >> s;
int l = s[0] - 'A' + 1, r = s[2] - 'A' + 1;
if(flag) continue;
if(g[r][l] || l == r)
{
flag = true;
printf("Inconsistency found after %d relations.\n", i);
continue;
// break; // WRONG 2
}
g[l][r] = true;
floyd();
if(check())
{
flag = true;
printf("Sorted sequence determined after %d relations: ", i);
for(int i = n - 1; i >= 0; i -- ) cout << ch[i];
cout << "." << endl;
continue;
// break; // (x)
}
}
if(!flag) puts("Sorted sequence cannot be determined.");
}
return 0;
}