Cod sursa(job #1109653)

Utilizator mcip1977Muresan Ciprian mcip1977 Data 17 februarie 2014 14:16:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int X[50004];//vectorul de parcurgere din BF
int GI[50004];//gradele interioare
vector<int> V[50004];//listele de adiacenta
int n,m;//dimensiunile grafului

void sort_top_BF()
{
    int st,dr=0;
    for (int i = 1; i <= n; i++)//adaug in X varfurile de pornire (grad interior 0)
        if (GI[i] == 0) X[++dr] = i;
    st = 1;//porneste de la primul vf din X
    while (st <= dr)//cat timp mai am varfuri neparcurse
    {
        int v = X[st];//varful curent
        for (int i = 0; i < V[v].size(); i++)//parcurg lista lui v
           {
               int j = V[v][i];//varful din lista lui v de la pozitia i
               GI[j]--;//scad gradul lui j
               if (GI[j] == 0) //daca are gradul 0 (=>toti dinaintea lui au fost parcusi)
                  X[++dr] = j;//il adaug si pe j in X
           }
        st++;//trec la urmatorul nod din stanga lui X
    }

    for (int i = 1; i <= n; i++)
        fout<<X[i]<<" ";//afisez vectorul X
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        V[x].push_back(y);
        GI[y]++;
    }
    sort_top_BF();
    fin.close();
    fout.close();
    return 0;
}