Cod sursa(job #1573444)

Utilizator dinu_sergiuDinu Sergiu Andrei dinu_sergiu Data 19 ianuarie 2016 18:12:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <iostream>
#include <stack>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct nod
{   int info;
    nod *urm;
} *prim[50001];

int n,m;
stack<int> S;
int viz[50001];


inline void Addnod(int x, int y)
{
    nod *p=new nod;
    p->info=y;
    p->urm=prim[x];
    prim[x]=p;
}

bool Cauta(int x, int y)
{ nod *p;
  for(p=prim[x];p!=NULL;p=p->urm)
     if(p->info==y) return true;
  return false;
}

void Citire()
{   int i, x, y;
    fin>>n>>m;
    while(fin>>x>>y)
       if(!Cauta(x,y))
         Addnod(x, y);
}

void DFS(int x)
{  nod *p;
   viz[x]=1;
   for(p=prim[x];p!=NULL;p=p->urm)
      if(viz[p->info]==0) DFS(p->info);
   S.push(x);
}

int main()
{   Citire();
    int i;
    for(i=1;i<=n;i++)
       if(viz[i]==0) DFS(i);
    while(!S.empty())
       {   fout<<S.top()<<" ";
           S.pop();
       }

    fin.close();
    fout.close();
    return 0;
}