Cod sursa(job #1850209)

Utilizator TrascaAndreiTrasca Andrei TrascaAndrei Data 18 ianuarie 2017 12:35:43
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

const int N = 50005;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n,m,deg[N];
vector<int> a[N];
deque<int> q;

void cit(){
    fin>>n>>m;
    int i,j,k;
    for(k=1;k<=m;k++){
        fin>>i>>j;
        a[i].push_back(j);
        deg[j]++;
    }
}

void sTop(){
    int i,x;
    for(i=1;i<=n;i++)
        if(deg[i]==0)
            q.push_back(i);

    for(i=1;i<=n;i++){
        x=q[i-1];
        for(auto it : a[x]){
            deg[it]--;
            if(deg[it]==0)
                q.push_back(it);
        }
    }
}


int main()
{
    cit();
    sTop();
    for(int i=1;i<=n;i++){
        fout<<q.front()<<" ";
        q.pop_front();
    }
    return 0;
}