Cod sursa(job #650198)

Utilizator EstarDaian Dragos Estar Data 17 decembrie 2011 15:40:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>

using namespace std;

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

struct noduri {
    vector<int> next;
    int i;
    noduri(int j){
        i=j;
    }
};

bool sir[50000];

int main() {
    int n , m,i=0;
    vector<noduri> nod;
    vector<int> coada;
    fi>>n>>m;
    for(int i=0;i<n;i++)
    nod.push_back(noduri(i));
    for(int i=0;i<m;i++){
        int x , y;
        fi>>x>>y;
        nod[x-1].next.push_back(y-1);
        sir[y-1]=true;
    }
    for(int i=0;i<n;i++)
    if(!sir[i])coada.push_back(i);
    for(;i<(signed)coada.size();i++){
        fo<<coada[i]+1<<' ';
        for(int j=0;j<(signed)nod[coada[i]].next.size();j++){
            if(sir[nod[coada[i]].next[j]]){
                sir[nod[coada[i]].next[j]]=false;
                coada.push_back(nod[coada[i]].next[j]);
            }
        }
    }
}