Cod sursa(job #1279740)

Utilizator DragodanAlexandraDragodan Alexandra DragodanAlexandra Data 30 noiembrie 2014 20:35:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

int n,m,Q[50001],ext[50001];
vector<int> A[50001];


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

void rezolvare ()
{
    int i,x;
    vector<int>::iterator it;
    for(i=1;i<=n;i++) if(ext[i]==0) Q[++Q[0]]=i;

    for(i=1;i<=n;i++)
    {
        x=Q[i];
        for(it=A[x].begin();it!=A[x].end();it++)
        {
            ext[*it]--;
            if(ext[*it]==0) Q[++Q[0]]=*it;
        }
    }
}

void afisare()
{
    int i;
    for(i=1;i<=Q[0];i++) printf("%d ",Q[i]);
}

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