Cod sursa(job #1442939)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 26 mai 2015 16:10:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <queue>
#include <vector>
#define nmax 100500

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

vector <int> graf[nmax], ordine;
bool v[nmax];
int N, M;
int main()
{int i, j, k, a, b;
    f>>N>>M;

    for(i = 1; i <= M; ++i){
        f>>a>>b;
        graf[b].push_back(a);
    }

    while(ordine.size() != N){
        for(i = 1; i <= N; ++i){
            if( graf[i].size() == 0 && !v[i]){
                ordine.push_back(i);
                v[i] = true;
            }
        }
        for(j = 1; j <= N; ++j)
                for(k = 0; k < graf[j].size(); ++k){
                    if(v[graf[j][k]]){
                        graf[j].erase(graf[j].begin() + k);
                        break;
                    }
                }
    }

    for(i = 0; i < ordine.size(); ++i)
        g<<ordine[i]<<' ';
    g<<'\n';
    return 0;
}