Cod sursa(job #645061)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 8 decembrie 2011 11:08:18
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>
using namespace std;

const int N=50010;

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

int n,m,q[N],nr,grad[N];
vector<int> g[N];
bool viz[N];

void bf() {
    int i;
    vector<int>::iterator it;

    for(i=1;i<=n;++i) {

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

            grad[*it]--;

            if(grad[*it]==0)
                q[++nr]=*it;
        }
    }
}

int main() {
    int i,a,b;

    in >> n >> m;

    for(i=1;i<=n;++i) {
        in >> a >> b;

        g[a].push_back(b);
        grad[b]++;
    }

    for(i=1;i<=n;++i) if(grad[i]==0)
        q[++nr]=i;

    bf();

    for(i=1;i<=n;++i)
        out << q[i] << " ";

    return 0;
}