Cod sursa(job #411766)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 martie 2010 09:54:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <vector.h>
#include <deque>
#define saiz 100010

using namespace std;

vector <int> vec[saiz];
deque <int> rez;
int grad[saiz];
int n,m;
int viz[saiz];

void citire()
{
    int a,b;
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d",&a,&b);
        grad[b]++;
        vec[a].push_back(b);
    }

    for (int i=1;i<=n;i++)
        if (grad[i]==0)
        {
            rez.push_front(i);
            viz[i]=1;
        }
}

void solve()
{
    int p1;
    for (int i=0;i<rez.size();i++)
    {
        p1=rez[i];
        for (int j=0;j<vec[p1].size();j++)
            if (!viz[vec[p1][j]])
            {
                grad[vec[p1][j]]--;
                if (grad[vec[p1][j]]==0)
                {
                    rez.push_back(vec[p1][j]);
                    viz[vec[p1][j]]=1;
                }
            }
    }

        for (int i=0;i<rez.size();i++)
            printf("%d ",rez[i]);
    printf("\n");
}

int main ()
{
    freopen ("sortaret.in","r",stdin);
    freopen ("sortaret.out","w",stdout);
    citire();
    solve();
    return 0;
}