Cod sursa(job #253947)

Utilizator mihai.cuculiciCuculici Mihail mihai.cuculici Data 6 februarie 2009 13:48:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<vector>
using namespace std;
#define NMAX 100010
ifstream f ("sortaret.in");
ofstream g ("sortaret.out");
vector <int> A[NMAX];
int viz[NMAX], N, M, x, y, i, nr=0;
typedef struct nod* Nod;
struct nod
{
   int Key;
   Nod Next; 
};

Nod V[NMAX];
Nod p2=NULL,c2=NULL;
void add(Nod &dest, int val)   
{     
    Nod p = new nod;   
    p->Key = val;   
    p->Next = dest;   
    dest = p;   
}   

void push(int x)
{
     c2=new nod;
     c2->Key=x;
     c2->Next=p2;
     p2=c2;
}

void write()
{
     for(;p2;p2=p2->Next) g<<p2->Key<<" ";
     g<<"\n";
}

void dfs(int x)
{
     viz[x]=1;
     for(Nod p3=V[x];p3;p3=p3->Next) if(!viz[p3->Key]) dfs(p3->Key);
     push(x);
}

int main()
{
    f>>N>>M;
    for(i=1;i<=M;i++) f>>x>>y, add(V[x], y);
    for(i=1;i<=N;i++) if(!viz[i]) dfs(i);
    write();
    g.close();
    return 0;
}