Cod sursa(job #1156986)

Utilizator raduiulianRadu Iulian Mihai raduiulian Data 28 martie 2014 10:23:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> a[50005];
int coada[50005],prim,ultim,n,m,x,y,g[50005];

struct punct
{
    int c1,c2;
}graf[100005];


int cmp(punct r,punct t)
{
    return r.c1<t.c1||r.c1==t.c1&&r.c2<t.c2;
}

void lee(int k)
{


    if(prim==ultim)
        return;
    printf("%d ",k);
    int nr=a[k].size();
    for(int i=0;i<nr;i++)
    {
        g[a[k][i]]--;
        if(g[a[k][i]]==0)
        {
            coada[ultim]=a[k][i];
            ultim++;
        }
    }
    prim++;
    lee(coada[prim]);
}



int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&graf[i].c1,&graf[i].c2);
    }
    sort(graf+1,graf+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(graf[i].c1!=graf[i-1].c1||graf[i].c2!=graf[i-1].c2)
        {
            a[graf[i].c1].push_back(graf[i].c2);
            g[graf[i].c2]++;
        }
    }
    ultim=1;
    for(int i=1;i<=n;i++)
    {
        if(g[i]==0)
        {
            coada[ultim]=i;
            ultim++;
        }
    }
    prim=1;
    lee(coada[prim]);
    return 0;
}