ACMclub - 1123 确定排序序列（拓扑排序）

本文主要是介绍ACMclub - 1123 确定排序序列（拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接

三种情况

1、成环矛盾

2、不能确定排序

3、确定

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int N, M;
const int MAXN = 27, MAXM = 1000;
int g[MAXN][MAXN], in[MAXN],  ans[MAXN];
int topoSort()
{int in1[MAXN];for(int i = 0; i < N; i++) in1[i] = in[i];for(int k = 0; k < N; k++){int i = 0;while(in1[i]!=0){i++;if(i >= N)return 2;	//成环，矛盾}ans[k] = i;in1[i]--;for(int j = 0; j < N; j++)if(g[i][j])in1[j]--;}for(int i = 0; i < N-1; i++){int ok = 0;//for(int j = 0; j < N; j++)if(g[ans[i]][ans[i+1]])ok = 1;if(!ok)return 1;	//不能确定排列序列}return 0;			//确定排序
}
int main()
{//freopen("in.txt", "r", stdin);while(scanf("%d%d", &N, &M)!=EOF && !(!N&&!M)){memset(g, 0, sizeof(g));memset(in, 0, sizeof(in));char s[10];int next = 0;for(int i = 0; i < M; i++){scanf("%s", s);if(next)continue;int u = s[0] - 'A', v = s[2] - 'A';g[u][v] = 1;in[v]++;int r = topoSort();if(r == 0){printf("Sorted sequence determined after %d relations: ", i+1);for(int j = 0; j < N; j++) printf("%c", ans[j]+'A');printf(".\n");next = 1;continue;}else if(r == 1 && i == M-1)printf("Sorted sequence cannot be determined.\n");else if(r == 2){printf("Inconsistency found after %d relations.\n", i+1);next = 1;continue;}}}return 0;
}

这篇关于ACMclub - 1123 确定排序序列（拓扑排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---