Cod sursa(job #2785451)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 18 octombrie 2021 18:23:42
Problema Sortare topologica Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
using namespace std;
int n,m;
const int N=50001;
ifstream Gigi ("sortaret.in");
ofstream Marcel ("sortaret.out");
struct nod
{
    int val=0;
    int k=0;
    vector <int> vec;
};
vector <nod> v;
vector <int> descos;
void scoate (int p)
{
    for (int i=1;i<v.size();i++){
        for (int j=0;j<v[i].k;j++){
            if (v[i].vec[j]==p){
                v[i].vec.erase(v[i].vec.begin()+j);
                v[i].k--;
                j--;
            }
        }
    }
}
int main()
{
    Gigi>>n>>m;
    nod temp;
    int x,y,i;
    temp.val=0;
    temp.k=-1;
    v.push_back(temp);
    temp.k=0;
    for (i=1;i<=n;i++){
        temp.val=i;
        v.push_back(temp);
    }
    for (i=0;i<m;i++){
        Gigi>>x>>y;
        v[y].val=y;
        v[y].k++;
        v[y].vec.push_back(x);
    }
    bool b=1;
    while (b){
        b=0;
        for (i=1;i<v.size();i++){
            if (v[i].k==0){
                b=1;
                v[i].k=-1;
                descos.push_back(i);
            }
        }
        while(!descos.empty()){
            Marcel<<v[descos.back()].val<<" ";
            scoate(v[descos.back()].val);
            v.erase(v.begin()+descos.back());
            descos.pop_back();
        }
    }
    return 0;
}