SCC or Kosaraju's algorithm

[anjaly grace]

//This code works for turbo c++
//Solution for strongly connected components or Kosaraju's algorithm
//for nitc students
//I use this because there is no other way i know how to do post a //code.




///////code:-


#include<iostream.h>
//#include<math.h>
#include<conio.h>

//int time;
//time=0;
char color[10];
int s[10];
int f[10];
int nn;
int fin[20];

 struct node
 {
 int no;
 node* next;
 }*beg,*np,*np1,*temp,*temp1,*temp2;

node *graph[50];
node *grapht[50];

node* createnxtn(int n)
{
 np=new node;
 np->no=n;
 np->next=NULL;
 return np;
}

void insert(node* np)
{
 if(beg==NULL)
 { beg=np;
   }
 else
 {
  temp=beg;
  beg=np;
  np->next=temp;
 }
}

void display(node* np)
{
 while(np!=NULL)
 {
  cout<<np->no<<"-";
  np=np->next;
 }
}

void del(node*np,node*np1)
{
 np->next=np1->next;
 delete np1;
  }

 void visit(int j,node *a[])
{
  color[j]='g';
 //time=time+1;
 //s[j]=time;
 temp=a[j];
 while(temp!=NULL)
 {
   int v=temp->no;
      if(color[v]=='w')
       {
    visit(v,a);
    temp=a[j]->next;
       }
      else
      {
      temp=temp->next; }
  }
 cout<<j<<",";
 color[j]='b';
 //time=time+1;
// f[j]=time;
}

void dfs(int n,node *a[])
{
  for(int j=1;j<=n;j++)
 {
  color[j]='w';
  }
 for(int i=1;i<=n;i++)
  {
   if(color[i]=='w')
    visit(i,a);
  cout<<"\n";
  }
}

void trans(int n)
{
 for(int i=1;i<=n;i++)
 {
  color[i]='w';
  np=createnxtn(i);
  grapht[i]=np;
 }
  for(int j=1;j<=n;j++)
  {
  temp=graph[j]->next;
  while(temp!=NULL)
  {
  int x=temp->no;
  np=createnxtn(j);
  temp1=grapht[x];
  np->next=temp1->next;
  temp1->next=np;
  temp=temp->next;
  }
 }
}

void scc(int n)
{
 dfs(n,graph);
  for(int k=1;k<=n;k++)
  {
   color[k]='w';
   int t=f[k];
   fin[t]= k;
  }
 trans(n);
 for(k=(2*n);k>=1;k--)
  {
   if((fin[k]!=NULL)&&(color[fin[k]])=='w')
   {
    int z=fin[k];
    visit(z,grapht);
   cout<<"\n";
   }
  }
}






void crteG(int n)
{
int i=1;
char ch='y';
int sd;
nn=0;
int x=0;
while(i<=n)
{
cout<<"Enter no. of nodes adjacent to "<<i<<" ";
cin>>sd;
    while(x<sd)
   {
    cout<<"enter the ajacent node of node no:"<<i<<" ";
    cin>>nn;
    createnxtn(nn);
    insert(np);
     x++;
    }
  graph[i]=beg;
  beg=NULL;
     i++;
x=0;
}
}


int main()
{
int n;
cout<<"enter the no of nodes";
cin>>n;
crteG(n);
 scc(n);
getch();
return 0;
}