Cod sursa(job #1467064)

Utilizator pepsiMisaki Chan pepsi Data 2 august 2015 18:10:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb

#include <cstring>
#include <vector>
#include <fstream>
#include <iostream>
#define MAXN 50100

using namespace std;
int N, M, deg[MAXN], Q[MAXN]; vector<int> G[MAXN];int t=-1;
void solve(){
    int x;

for (int i=1;i<=N;i++){
    if (deg[i]==0)
        {
            Q[++t]=i;


        }
}
for (int i=0;i<N;i++){
    x=Q[i];


    for (vector<int> ::iterator it=G[x].begin();it !=G[x].end();++it){
        deg[*it]--;
        if (deg[*it]==0) Q[++t]=*it;
    }
}

}

void read_data(ifstream &f){
    int a,b;
    f>>N>>M;

    for (int i=0;i<M;i++){
   f>>a>>b;
   G[a].push_back(b);
deg[b]++;
    }
}
void write_data(ofstream &g){
for (int j=0;j<N;j++)
    g<<Q[j]<<' ';
    }



int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
read_data(f);
solve();
write_data(g);
    return 0;
}