Cod sursa(job #1302095)

Utilizator jordasIordache Andrei Alexandru jordas Data 26 decembrie 2014 16:47:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>

using namespace std;

 ifstream x ("sortaret.in");
 ofstream y ("sortaret.out");

 struct node
 {
     int data;
     node *next;
 };

 int N,M;
 int s[50001];
 bool v[50001];
 node *head[50001];
 node *temp;
 node *current;

int main()
{
    int i;

    x>>N>>M;

    int X,Y;

    for(i=1;i<=M;i++)
    {
        x>>X>>Y;

        if(head[X]==NULL)
        {
            head[X]=new node();
            head[X]->data=Y;
            head[X]->next=NULL;
        }
        else
        {
            temp=new node();
            temp=head[X];
            while(temp->next)
               temp=temp->next;
            current=new node();
            current->data=Y;
            current->next=NULL;
            temp->next=current;
        }
    }
/*
    for(i=1;i<=N;i++)
    {
        y<<i<<" --> ";

        current=head[i];
        while(current)
        {
            y<<current->data<<' ';
            current=current->next;
        }

        y<<'\n';
    }
    y<<"\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n";
*/
    bool flag;
    int k=0;

    while(k<N)
    {
        for(i=1;i<=N;i++)
        if(v[i]==false)
           if(head[i]==NULL)
           {
               v[i]=true;
               k++;
               s[k]=i;
           }
           else
           {
               flag=true;

               current=head[i];
               while(current)
               {
                   if(v[current->data]==false)
                   {
                       flag=false;
                       break;
                   }

                   current=current->next;
               }

               if(flag==true)
               {
                   v[i]=true;
                   k++;
                   s[k]=i;
               }
           }
    }

    for(i=k;i>=1;i--)
       y<<s[i]<<' ';
    y<<'\n';

    return 0;
}