#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define maxSize 100
//边表
typedef struct ArcNode
{
int adjvex; //该边所指向的结点的位置
struct ArcNode *nextarc; //指向下一条边的指针
int info; //该边的相关信息（如权值）
}ArcNode;
//顶点表
typedef struct
{
char data; //顶点信息
int count;
ArcNode *firstarc; //指向第一条边的指针
}VNode;
typedef struct
{
VNode adjlist[maxSize]; //邻接表
int n,e; //顶点数和边数
}AGraph;
void Create(AGraph *G)
{
cout<<"请输入顶点数和边数:"<<endl;
cin>>G->n>>G->e;
cout<<"输入顶点信息:"<<endl;
for(int i=0;i<G->n;i++)
{
getchar();
cin>>G->adjlist[i].data;
G->adjlist[i].firstarc=NULL; //指向边表的指针初始时置为空
G->adjlist[i].count=0;
}
ArcNode *p;
//建立边表
cout<<"输入边的下标:"<<endl;
for(int k=0;k<G->e;k++)
{
int i,j;
cin>>i>>j;
G->adjlist[j].count++;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j; //存储弧头
p->nextarc=G->adjlist[i].firstarc; //头插法插入边结点
G->adjlist[i].firstarc=p;
}
}
int TopSort(AGraph *G)
{
int i,j,n=0;
int stack[maxSize],top=-1;
ArcNode *p;
for(i=0;i<G->n;++i)
if(G->adjlist[i].count==0)
stack[++top]=i;
while(top!=-1)
{
i=stack[top--];
++n;
cout<<i<<" ";
p=G->adjlist[i].firstarc;
while(p!=NULL)
{
j=p->adjvex;
--(G->adjlist[j].count);
if(G->adjlist[j].count==0)
stack[++top]=j;
p=p->nextarc;
}
}
if(n==G->n)
return 1;
else
return 0;
}
/*
7 11
a b c d e f g
0 1 0 2 0 3
1 2 1 4 2 5 2 4
3 5 4 6 5 4 5 6
*/
int main()
{
AGraph G;
Create(&G);
TopSort(&G);
}
