Cod sursa(job #2143421)

Utilizator AndreiOffCovaci Andrei-Ion AndreiOff Data 25 februarie 2018 22:13:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <vector>
#include <fstream>
#define N_MAX 100001

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector<int> gr[N_MAX];
int nrTati[N_MAX], n, m, ordonare[N_MAX], aux, q[N_MAX];

void solve(){ //100 puncte

int x; vector<int>::iterator it;

for(int i=1; i<=n; i++)
    if(nrTati[i]==0) q[++q[0]]=i;
for(int i=1; i<=n; i++){

    x=q[i];
    for(it=gr[x].begin(); it!=gr[x].end(); it++){


        nrTati[*it]--;
        if(nrTati[*it]==0) q[++q[0]]=*it;

    }

}

}

int main(){ //principiul este ca la citire numar tatii fiecarui nod. Parcurg apoi vectorul si vad cine este radacina si o adaug in coada. Parcurg apoi fiecare fiu ai nodurilor care sunt in coada
    //si ii scad un tata (elimin un tata ca sa pot sa obtin urmatoarea serie de tati) daca un fiu nu mai are tati atunci el insusi e tata si il adaug in coada

f>>n>>m;
for(int i=1; i<=m; i++){

int x, y;
f>>x>>y;
gr[x].push_back(y);
nrTati[y]++;

}

solve();

for(int i=1; i<=q[0]; i++) g<<q[i]<<" ";
/*
while(n){ //50 puncte

for(int i=1; i<=aux; i++){

    if(nrFii[i] == 0){

        ordonare[n]=i;
        n--;
        nrFii[i]--;
     for(int j=1; j<=aux; j++)
         for(auto k: gr[j])
             if(k == i)
                 nrFii[j]--;
        }


}

}
vector<int>::iterator i;
for(i=gr[6].begin(); i!=gr[6].end(); i++)
    g<<*i<<" ";*/
}