#include<stdio.h>
int vertex,indegree1[50],strtop[50];
int graph[50][50];
void topo(int vertex);
int main()
{
int i,j,edge,p,x,y,kk,ff,rr;
printf("Enter the Number of Vertex : ");
scanf("%d",&vertex);
printf("\n");
printf("Enter the Number of Edge : ");
scanf("%d",&edge);
printf("\n");
for(ff=1;ff<=vertex;ff++)
for(rr=1;rr<=vertex;rr++)
graph[ff][rr]=0;
for(i=1;i<=edge;i++)
{
scanf("%d%d",&x,&y);
graph[x][y]=1;
}
for(kk=1;kk<=vertex;kk++)
{ indegree1[kk]=0;
strtop[kk]=0;
}
printf("\n");
for(i=1;i<=vertex;i++)
for(j=1;j<=vertex;j++)
if(graph[j][i]==1)
indegree1[i]++;
topo(vertex);
return 0;
}
void topo(int vertex)
{
int l,p,xx,node,top=0,d=0,flag=0,pp;
for(l=1;l<=vertex;l++)
{
if(indegree1[l]==0)
{
strtop[++top]=l;
flag=1;
}
}
if(flag==0)
{ printf("Topological sort is not possible\n");
}
else
{
while(d!=vertex)
{
node=strtop[++d];
for(xx=1;xx<=vertex;xx++)
if(graph[node][xx]==1)
{
indegree1[xx]=indegree1[xx]-1;
if(indegree1[xx]==0)
strtop[++top]=xx;
}
}
printf("\nAfter topological sort : \n");
for(pp=1;pp<=vertex;pp++)
printf("%d ",strtop[pp]);
printf("\n");
}
}