拓扑排序,好麻烦的说
code
/*
ID: yueqiq
PROG: numtri
LANG: C++
*/
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 102;
const int INF = 0x3fffffff;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
const double eps= 1e-7;
using namespace std;
//A=0,B=1,........
int N,M;
int indegree[26];
bool link[26][26];
int path[26],cnt;
int topsort(){
int zero_cnt=0;
int zeronode;
int in[26];
FF(i,26){ in[i]=indegree[i];
//printf(" i:%d in:%d\n",i,in[i]);
}
bool flag=false;
cnt=0;
SET(path,0);
FF(i,N){
// puts("--------------------------");
// FF(j,N){
// printf(" i:%d in:%d\n",j,in[j]);
// }
// puts("--------------------------");
zero_cnt=0;
FF(j,N){
if(in[j]==0){
zero_cnt++;
zeronode=j;
//PD(j);LN;
}
}
//printf("zerocnt: %d zeronode:%d \n",zero_cnt,zeronode);
if(zero_cnt==0) return -1;//loop occur;
if(zero_cnt>1) flag=true;//ambigous
in[zeronode]=-1;
FF(j,N){
if(link[zeronode][j])
in[j]--;
}
path[cnt++]=zeronode;
}
if(flag) return 1;
return 0;
}
int main()
{
char t[3];
int a,b;
while(~scanf("%d%d",&N,&M)&&(N+M)){
SET(link,false);SET(indegree,0);
int k=1,step=1;
FOR(i,1,M){
scanf("%s",t);
a=t[0]-'A';
b=t[2]-'A';
indegree[b]++;
link[a][b]=true;
if(k==1){
k=topsort();
step=i;
}
//PD(k);LN;
}
if(k==0){
printf("Sorted sequence determined after %d relations: ",step);
FF(i,cnt){
printf("%c",(char)(path[i]+'A'));
}
puts(".");
}else if(k==-1){
printf("Inconsistency found after %d relations.\n",step);
}else{
puts("Sorted sequence cannot be determined.");
}
}
return 0;
}
分享到:
相关推荐
北大POJ1094-Sorting It All Out 解题报告+AC代码
poj 1091 拓扑排序加上foyld_warshall算法实现
NULL 博文链接:https://200830740306.iteye.com/blog/603488
DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...
poj dna sorting 问题,研究的ac coderrrrrrr
北大POJ1936-All in All 解题报告+AC代码
北大POJ1007-DNA Sorting 解题报告+AC代码
poj 2409 Let it Bead.md
poj 1308 Is It A Tree_.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 百练 题目分类 poj 百练 题目分类