Cod sursa(job #1009701)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 13 octombrie 2013 18:01:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include "stdio.h"
#include <queue>
#include <vector>

int main ()
{
    FILE* fin=fopen("sortaret.in","r");
    FILE* fout=fopen("sortaret.out","w");
    int i,n,m,a,b; 
    fscanf(fin,"%d %d",&n,&m); 
    
    std::vector<std::vector<int> > g;
    std::vector<bool> leaf(n+1,true);
    std::vector<int> count(n+1,0);
    std::vector<int> result;
    for(i=0;i<m;i++)
    {
        fscanf(fin,"%d %d",&a,&b);
        if(b>=g.size())
        { g.resize(b+1);
        }
        g[b].push_back(a);  
        count[a]++;
        leaf[a]=false;
    } 
    std::queue<int> q;
    for(i=1;i<=n;i++)
    {   if(leaf[i])
        {   q.push(i);
        }
    } 
    while(q.size()>0)
    {
        int x=q.front();q.pop();
        result.push_back(x);
        for(i=0;i<g[x].size();i++)
        {   int parent=g[x][i];
            count[parent]--;
            if(count[parent]==0)
            {   q.push(parent);  
            } 
        } 
    }
    for(i=result.size()-1;i>=0;i--)
    {
        fprintf(fout,"%d ", result[i]);
    }
    fclose(fout);
    fclose(fin);
    return 0;
}