Cod sursa(job #953103)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 24 mai 2013 21:20:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<cstdio>
#include<vector>
#define nx 50007
using namespace std;
int n,m,i,j,u,x,y,w[nx],d[nx],viz[nx];
vector<int>v[nx];
bool ok;

void ver()
{
    u=1;
    while(u!=0){
    u=0;
    for(i=n;i>=1;i--)
    if(d[i]==0 && viz[i]==0)u++,w[u]=i,viz[i]=1,printf("%d ",i);

    for(i=1;i<=u;i++)
    for(j=0;j<v[w[i]].size();j++)
    d[v[w[i]][j]]--;
    }
}

void citire()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        ok=true;
        for(j=0;j<v[x].size();j++)if(v[x][j]==y){ok=false;break;}
        if(ok==true)v[x].push_back(y),d[y]++;
    }
}

int main()
{
    citire();
    ver();
    return 0;
}