Cod sursa(job #1255874)

Utilizator Laura.miLaura Mitrache Laura.mi Data 5 noiembrie 2014 13:46:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int viz[50004];
int q[50004];
int grad[50004];
vector <int> L[50002];
int n,m;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
 
void Citire()
{
    f>>n>>m;
    int i,x,y;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        L[x].push_back(y);
        grad[y]++;
    }
    f.close();
}
void Solve()
{
    int pr,ul,i,j;
    //Initializare coada
    pr=1;
    ul=0;
    for (i=1;i<=n;i++)
    {
        if(grad[i]==0)
            q[++ul]=i;
    }
    while(pr<=ul)
    {
        int x;
        x=q[pr++];
        for(i=0;i<L[x].size();i++)
        {
            grad[L[x][i]]--;
            if(grad[L[x][i]] == 0)
                q[++ul]=L[x][i];
        }
    }
 
 
}
void Anzeige()
{
    int i;
    for(i=1;i<=n;i++)
        g<<q[i]<<"\n";
    g.close();
}
int main()
{
   Citire();
   Solve();
   Anzeige();
    return 0;
}