Cod sursa(job #1327075)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 26 ianuarie 2015 12:55:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <vector>
std::vector<int> *adj;
int in[50001],a[50001];
int n,m;
bool fol[50001];
int main()
{
    freopen ("sortaret.in","r",stdin);
    freopen ("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    adj=new std::vector<int> [n+1];
    int p1,p2;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d",&p1,&p2);
            in[p2]++;
            adj[p1].push_back(p2);
    }
    int pos=1;
    for(int i=1;i<=n;i++)
    {
            if(in[i]==0)
            {
                        a[pos]=i;
                        fol[i]=1;
                        pos++;
            }
    }
    for(int i=1;i<pos;i++)
    {
            while(!adj[a[i]].empty())
            {
                                     in[adj[a[i]].back()]--;
                                     if(in[adj[a[i]].back()]==0)
                                     {
                                                              a[pos]=adj[a[i]].back();
                                                              pos++;
                                     }
                                     adj[a[i]].pop_back();
            }
            
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}