#include<iostream>
#define OK 1
using namespace std;
const int MAX=1e5;
const int maxn=1e2+10;
const int dot=11;//点的个数；
int aov[maxn][maxn];//存图；
int voa[maxn][maxn];//逆邻接表；
int vis[maxn];//存每个点的入度；
int dis[maxn];//存拓扑序列；
typedef int status;
typedef int person;
typedef struct
{int *base;int front;int rear;
}squeue;
squeue Mdancer,Fdancer;
void initqueue(squeue &Q)//建立
{Q.base=new person[MAX];Q.front=Q.rear=0;
}
void enqueue(squeue &Q,int &e) //入队
{Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAX;
}
void dequeue(squeue &Q,int &e) //出队
{e=Q.base[Q.front];Q.front=(Q.front+1)%MAX;
}
person gethead(squeue Q) //队头元素
{if(Q.front!=Q.rear) return Q.base[Q.front];
}
status queueempty(squeue Q) //判断队列是否为空
{if(Q.front!=Q.rear)return 0;else return OK;
}
void cou()
{cout<<"设计一个软件需要进行的一系列活动:"<<endl; cout<<endl;cout<<"A1:用户需求分析"<<endl;cout<<"A2:系统需求确认"<<endl;cout<<"A3:系统概要设计"<<endl;cout<<"A4:设计用例场景"<<endl;cout<<"A5:系统的详细设计"<<endl;cout<<"A6:数据库详细设计"<<endl;cout<<"A7:编码"<<endl;cout<<"A8:单元测试"<<endl;cout<<"A9:集成测试"<<endl;cout<<"A10:系统测试"<<endl;cout<<"A11:维护"<<endl;cout<<"可使用额外的活动，A11,A12...等"<<endl;cout<<endl;
}
void cot()
{int n; int x,y;cout<<"设计一个软件需要进行的系列活动之间的关系"<<endl;cout<<"请输入活动关系个数："<<endl;cin>>n;cout<<"输如活动之间的关系："<<endl; cout<<"例如：完成活动A1需要先完成活动A2，则输入2 1:"<<endl;for(int i=0;i<n;i++){scanf("%d%d",&x,&y); while(!(x>=1&&x<=dot&&y>=1&&y<=dot)){cout<<"输入错误，请重新输入:"<<endl;scanf("%d%d",&x,&y);} aov[x][y]=1;voa[y][x]=1; vis[y]++;}cout<<endl;cout<<"aov邻接表为："<<endl;for(int i=1;i<=dot;i++){cout<<i<<":";for(int j=1;j<=dot;j++)if(aov[i][j])cout<<" "<<j;cout<<endl;}cout<<endl;for(int i=1;i<=dot;i++){cout<<"完成A"<<i<<"需要先完成活动:";for(int j=1;j<=dot;j++)if(voa[i][j])cout<<" A"<<j;cout<<"共"<<vis[i]<<"个活动"<<endl; } cout<<endl;
}
int tp()//拓扑排序
{squeue Q;int e;int k=0; initqueue(Q);for(int i=1;i<=dot;i++){if(!vis[i]){enqueue(Q,i);}}while(!queueempty(Q)){dequeue(Q,e);dis[k++]=e;for(int i=1;i<=dot;i++){if(aov[e][i]){vis[i]--;if(!vis[i])enqueue(Q,i); }}}return k;
}
int main()
{cou();cot();if(tp()==dot){cout<<"拓朴序列为：";for(int i=0;i<dot;i++)cout<<"A"<<dis[i]<<", ";}elsecout<<"该系列活动存在环"<<endl; return 0;
}
/*
12
1 2
2 3
4 5
3 5
3 6
5 7
6 7
7 8
7 10
8 9
9 11
10 11
*/