Cod sursa(job #1326837)

Utilizator theprdvtheprdv theprdv Data 26 ianuarie 2015 02:31:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
fstream fout("sortaret.out", ios::out);

int n, m, in[50100];
queue <int> q;
struct node{
    int inf;
    node *next;
};
struct node *list[50100];
void add(node *&root, int n){
    node *elem=new node;
    elem->inf=n;
    elem->next=root;
    root=elem;
}
void read(){
    fstream fin("sortaret.in", ios::in);
    fin>>n>>m;
    for(int i=1; i<=n; i++){
        int x, y;
        fin>>x>>y;
        add(list[x], y);
        in[y]++;
    }
    fin.close();
}
void del(node *&root){
    while(root){
        if(!--in[root->inf])
            q.push(root->inf);
        node *del_n=root;
        root=root->next;
        delete del_n;
    }
}
void topological_sort()
{
    for(int i=1; i<=n; i++)
        if(!in[i]) q.push(i);
    while(q.size()!=0){
        int n=q.front();
        cout<<n<<" ";
        q.pop();
        del(list[n]);
    }
}
int main()
{
    read();
    topological_sort();
    fout.close();
    return 0;
}