Cod sursa(job #1006461)

Utilizator lukkerLiNoimi Semain lukker Data 7 octombrie 2013 08:45:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct point {
    vector<int> child;
    int grad;
    bool used;
};

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<point> p;
vector<int> sol;

void f() {
    int pt;
    for(int i=0;i<(int)p.size();i++) {
        pt=sol[i];
        for(int k=0;k<(int)p[pt].child.size();k++) {
            p[p[pt].child[k]].grad--;
            if(p[p[pt].child[k]].grad==0) sol.push_back(p[pt].child[k]);
        }
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    point a;
    a.grad = 0;
    a.used = false;
    p.resize(n+1, a);
    while(m-->0) {
        int x,y;
        fin>>x>>y;
        p[x].child.push_back(y);
        p[y].grad++;
    }
    for(int i=1;i<=n;i++) {
        if(p[i].grad == 0) sol.push_back(i);
    }
    f();
    for(int i=0;i<n;i++) {
        fout<<sol[i]<<" ";
    }

    return 0;
}