topological sort

topologicalsort.cpp

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int adj[10][10];
vector<int> indegree;
vector<int> order;
queue<int> q;
void create_graph(int n)
{
    int x,max_ver,i,j,k,src,dest;

      for(j=0;j<n;j++)
     {
         for(k=0;k<n;k++)
         {
             adj[j][k]=0;
         }
     }
     cout<<"press 1 for undirected graph and 2 for directed graph \n";
     cin>>x;
         if(x==1)
            max_ver=n*(n-1)/2;
         else
            max_ver=n*(n-1);

     for(i=0;i<max_ver;i++)
     {
         cout<<"enter the source and destination \n";
         cin>>src>>dest;
         if(src==-1&&dest==-1)
            break;
         if(src<0||src>=n||dest<0||dest>=n)
         {
             cout<<"invalid vertex \n";
             i--;
         }

         adj[src][dest]=1;
         if(x==1)
         adj[dest][src]=1;
     }

     for(j=0;j<n;j++)
     {
         for(k=0;k<n;k++)
         {
             cout<<adj[j][k]<<"\t";
         }
         cout<<endl;
     }
}

int main()
{
    int n,s,z,v,i,j,sum=0,c=0;
    vector<int>::iterator it;
    cout<<"enter the no of vertices \n";
    cin>>n;
    create_graph(n);
    for(i=0;i<n;i++)
    {
        sum=0;
        for(j=0;j<n;j++)
        {
            sum=sum+adj[j][i];
        }
        indegree.push_back(sum);
        if(sum==0)
            q.push(i);
    }
    while(!q.empty()&&c<n)
    {
        int x=q.front();
        q.pop();
        order.push_back(x);
        c++;
        for(i=0;i<n;i++)
        {
            if(adj[x][i]==1)
            {
                adj[x][i]=0;
                indegree[i]=indegree[i]-1;
                if(indegree[i]==0)
                    q.push(i);
            }
        }
    }
    if(c<n)
        cout<<"\n no order possible and cycle exists";
    else
        for(it=order.begin();it!=order.end();it++)
    {
        cout<<*it<<"\t";
    }
}