Topological Sort

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
struct adjnode
{
char dest;
adjnode *link;
};
struct node
{
char data;
int degree;
int q;
node *next;
adjnode *adj;
};

node *first,*last,*start;
int n,flag;
int rear,front;
char queue[50];
void enteradj(node* ptr)
{ int nadj;
cout<<” no of adjacent node present??”;
cin>>nadj;

if(nadj>0)
{
adjnode *beg,*end;
beg=new(adjnode);
ptr->adj=beg;
cout<<“enter the first adjacent member/destination”;
cin>>beg->dest;
beg->link=NULL;
for(int a=1;a<nadj;a++)
{
end=new(adjnode);
cout<<“enter destination”;
cin>>end->dest;
fflush(stdin);
end->link=NULL;
beg->link=end;
beg=end;
}
}
else
{
ptr->adj=NULL;
}
}
void calculatedegree()
{ node *n;
adjnode *ptr;
n=start;
while(n!=NULL)
{

ptr=n->adj;
while(ptr!=NULL)
{
ptr=ptr->link;
n->degree++;
}
cout<<“\n “<<n->degree;
n=n->next;
}
}

void insert(int flag)
{ node *ptr;
ptr=start;
while(ptr!=NULL)
{
if((ptr->degree==0)&&(flag==1))
{queue[rear]=ptr->data;
ptr->q=1;

cout<<“\n the data entered is”<<queue[rear];
rear++;
}
else
{
if((ptr->degree==0)&&(ptr->q==0))
{
queue[rear]=ptr->data;
ptr->q=1;

cout<<“entered data is”<<queue[rear];
rear++;
}
}
ptr=ptr->next;
}
}
node* find(char info)
{
node *ptr;
ptr=start;
while(ptr!=NULL)
{
if(ptr->data==info)
{
break;
}
ptr=ptr->next;
}
return ptr;
}
void adjcalculate(char info)
{
node *loc,*loc1;
loc=find(info);
adjnode *p;
p=loc->adj;
while(p!=NULL)
{
loc1= find(p->dest);
loc1->degree–;
cout<<“degree of adjacent members : “<<loc1->degree;
p=p->link;
cout<<“\n”;

}
}

int main()
{
clrscr();
cout<<“enter n”;
cin>>n;
first=new(node);
cout<<“enter the first data”;
cin>>first->data;
first->next=NULL;
start=first;
fflush(stdin);
enteradj(first);
cout<<“enter degree”;
cin>>first->degree;
first->q=0;
for(int b=1;b<n;b++)
{
last=new(node);
cout<<“enter the data of node”;
cin>>last->data;
fflush(stdin);
enteradj(last);
last->next=NULL;
cout<<“enter degree”;
cin>>last->degree;
last->q=0;
first->next=last;
first=last;
}
char temp;
front=rear=0;
flag=1;
while(front<=rear)
{
insert(flag);
temp=queue[front];
front++;
cout<<“rear is”<<rear;
adjcalculate(temp);
flag=0;
}
cout<<“rear is”<<rear;
int j=0;
while(j<=rear)
{
cout<<queue[j];
j++;
cout<<“\n”;
}
getch();
return 0;
}