#include<iostream>
#include<fstream>
#include<stack>
usingnamespace std;
constint MAX=100;
struct ArcNode
{
int adjVNode; //节点编号
ArcNode *nextArcNode; // 指向邻接到同一节点的其他节点
ArcNode(){nextArcNode=NULL;}
};
struct VNode
{
int num; //节点编号
ArcNode *firstArcNode; //指向该节点邻接的节点
VNode(){firstArcNode=NULL;}
};
struct Graph
{
int vexnum; //图点数
int arcnum; //图边数
VNode vertices[MAX]; //图的邻接表，指针数组
};
bool topSort(Graph G, int *indegree,int *TopNum)
{
int count=0;
stack<int> Q;
for(int i=0;i<G.vexnum;i++)
{
if(indegree[i]==0)
Q.push(i);
}
while(!Q.empty())
{
int u=Q.top();
Q.pop();
TopNum[u]=++count;
ArcNode *p;
for(p=G.vertices[u].firstArcNode;p!=NULL;p=p->nextArcNode)
{
indegree[p->adjVNode]--;
if(indegree[p->adjVNode]==0)
Q.push(p->adjVNode);
}
}
if(count!=G.vexnum)
returnfalse;
returntrue;
}
int main()
{
Graph G;
ifstream fin("in.txt");
cout<<"输入节点数和边数： ";
cin >> G.vexnum >> G.arcnum;
//G.vertices=new VNode[G.vexnum];
for(int i=0;i<G.vexnum;i++)
{
G.vertices[i].num=i;
}
ArcNode *p;
int *indegree=newint[G.vexnum];
for(int i=0;i<G.arcnum;i++)
indegree[i]=0;
for(int i=0;i<G.arcnum;i++)
{
int u,v;
cout<<"第"<<i+1<<"条边：";
//cin >> u >> v;
cin >> u >> v;
p=new ArcNode();
p->adjVNode=v-1;
p->nextArcNode=G.vertices[u-1].firstArcNode;
G.vertices[u-1].firstArcNode=p;
indegree[v-1]++;
//cout << endl;
}
int *TopNum=newint[G.vexnum];
if(topSort(G,indegree,TopNum))
{
for (int i=0;i<G.vexnum-1;i++)
{
cout<<TopNum[i]<<"->";
}
cout<<TopNum[G.vexnum-1]<<endl;
}
system("pause");
return 0;
}。