模板题:http://poj.org/problem?id=1094
思路:
找度为0的元素,入列查找关系
对应关系减度
反复直到队列为空
没太多可说的,难点是应用涉及aoe网,关键路径的那种
大佬代码
#include <iostream> #include <cstdio> #include <queue> #include <cstdlib> #include <cstring> using namespace std; int n,m; int mp[110][110],in[110],list[110],tm[110];//mp存储关系,in记录初始y的度 ,list是排序存储的空间,tm存储一直延续的度 int toopsort() { queue<int>s; while(!s.empty()) { s.pop(); } int flag=0,j=0; memcpy(tm,in,sizeof(in)); for(int i=0;i<n;i++) { if(tm[i]==0) { s.push(i);//找出入度为0得点即为起始点 } } while(!s.empty()) { if(s.size()>1)//如果入度为零的点有很多,则很多点还没涉及到还处于初始化中,为1时才只有一个起始点 { flag=1;//不能确定关系则要继续进行 } int t=s.front(); s.pop(); list[j++]=t; for(int i=0;i<n;i++) { if(mp[t][i])//t和i有关系 { if(--tm[i]==0)//存储入度为0得点 { s.push(i); } } } } if(j!=n)//如果j>n则说明有环,应为处理完后加上初始化的入度为0得点应为n个 return 1; else if(flag)//无法确定关系继续 return 2; else return 0;//既没有环又没有不能确定关系的则完成 } int main() { int flag1,flag2; char x,y; while(~scanf("%d%d",&n,&m)&&n&&m) { getchar(); flag1=0; flag2=0; memset(mp,0,sizeof(mp)); memset(in,0,sizeof(in)); for(int i=1;i<=m;i++) { scanf("%c<%c",&x,&y);//即使有了结果也要保证全部输入完成 getchar(); if(!flag1&&!flag2)//用两个标记变量来确定 { if(mp[y-'A'][x-'A']==1)//xY和Yx都有,不符合条件 { printf("Inconsistency found after %d relations.",i); flag1=1; continue; } if(mp[x-'A'][y-'A']==0) { mp[x-'A'][y-'A']=1; in[y-'A']++; } int tmp=toopsort(); if(tmp==1) { printf("Inconsistency found after %d relations.",i); flag1=1; } else if(tmp==0) { flag2=1; printf("Sorted sequence determined after %d relations: ",i); for(int j=0;j<n;j++) { printf("%c",list[j]+'A'); } printf("."); } } } if(!flag1&&!flag2)//剩下的情况就是无法判定了 { printf("Sorted sequence cannot be determined."); } printf("\n"); } return 0; }