Cod sursa(job #901235)

Utilizator costi_.-.Costinnel costi_.-. Data 1 martie 2013 08:45:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#define nmax 50001
using namespace std;

struct nod_lista{
    int val;
    nod_lista *link;
};

nod_lista *G[nmax],*Last[nmax];
int st[nmax],viz[nmax],N,M,k;

void adauga(int unde,int ce)
{
    nod_lista *q=new nod_lista;
    q->val=ce;
    q->link=NULL;

    if(!G[unde])
    G[unde]=Last[unde]=q;
    else
    {
        Last[unde]->link=q;
        Last[unde]=q;
    }
}

void citeste()
{
    ifstream f("sortaret.in");
    int i,x,y;

    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>x>>y;
        adauga(x,y);
    }

    f.close();
}

void DF(int nod)
{
    nod_lista *q=G[nod];
    while(q)
    {
        if(!viz[q->val])
        {
            viz[q->val]=1;
            DF(q->val);
        }
        q=q->link;
    }
    st[++k]=nod;
}

void rezolva()
{
    int i;
    for(i=1;i<=N;i++)
    if(!viz[i])
    {
        viz[i]=1;
        DF(i);
    }
}

void scrie()
{
    ofstream g("sortaret.out");
    int i;

    for(i=k;i>=1;i--)
    g<<st[i]<<' ';

    g<<'\n';
    g.close();
}

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}