POJ - 1094(拓扑排序)

2024-01-03 12:38

文章标签 排序 poj 拓扑 1094

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

参考博客http://www.cppblog.com/infinity/archive/2008/11/06/66086.html

Sorting It All Out

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.

Sample Input

4 6
A

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

与原博客代码不同，有删改

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <functional>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int MAX=50+10;
const double eps=1e-6;int n,m,cnt;
int mapp[MAX][MAX],in_du[MAX];
char ans[MAX];int floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mapp[i][k]&&mapp[k][j])mapp[i][j]=1;}}}for(int i=1;i<=n;i++)if(mapp[i][i])  return 0;return 1;
}int tsort(){cnt=0;queue<int>q;memset(in_du,0,sizeof(in_du));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mapp[i][j])in_du[j]++;}}for(int i=1;i<=n;i++)if(!in_du[i])   q.push(i);while(q.size()){if(q.size()>1)  return 0;int u=q.front();q.pop();ans[cnt++]='A'+(u-1);for(int i=1;i<=n;i++){if(i==u)    continue;if(mapp[u][i]){in_du[i]--;if(!in_du[i])q.push(i);}}}ans[cnt]='\0';return 1;
}int main(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);#endifwhile(cin>>n>>m){if(n==m&&!n)    break;cnt=0;      memset(mapp,0,sizeof(mapp));int flag1=0,flag2=0;char t[5];for(int i=1;i<=m;i++){scanf("%s",t);int u=t[0]-'A'+1;int v=t[2]-'A'+1;mapp[u][v]=1;if(flag1||flag2)continue;else if(!floyd()){flag1=i;}else{if(tsort())flag2=i;}}if(flag1)   printf("Inconsistency found after %d relations.\n",flag1);else if(flag2)printf("Sorted sequence determined after %d relations: %s.\n",flag2,ans);elseprintf("Sorted sequence cannot be determined.\n");}return 0;
}