Cod sursa(job #2664807)

Utilizator MValentinMunteanu Valentin-Ioan MValentin Data 29 octombrie 2020 14:25:40
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector < vector <int> > g;
int dm[1004];

struct nod
{
    int info;
    nod *ant, *urm;
};

void adauga(nod * & p, int x)
{
    nod * p2 = p, * t = new nod;
    t -> info = x;
    if(p == NULL)
    {
        t -> urm = NULL;
        t -> ant = NULL;
        p = t;
    }
    else
    {
        while(p2 -> urm != NULL && dm[p2 -> info] < x)
            p2 = p2 -> urm;
        if(p2 -> info > x)
        {
            t -> ant = p2 -> ant;
            t -> urm = p2;
            p2 -> ant -> urm = t;
            p2 -> ant = t;
        }
        else
        {
            t -> urm = NULL;
            t -> ant = p2;
            p2 -> urm = t;
        }
    }
}

void eliminare(nod * & p, int x)
{
    nod * p2 = p;
    if(p -> info == x)
    {
        if(p -> urm == NULL)
            p = NULL;
        else
        {
            p = p -> urm;
            p -> ant = NULL;
        }
    }
    else
    {
        while(p2 -> info != x)
            p2 = p2 -> urm;
        if(p2 -> urm == NULL)
        {
            p2 -> ant -> urm = NULL;
            delete p2;
        }
        else
        {
            p2 -> ant -> urm = p2 -> urm;
            p2 -> urm -> ant = p2 -> ant;
            delete p2;
        }
    }
}

int main()
{
    nod * s = NULL, * z = NULL;
    int n, m, x, y, i, k;
    fin >> n >> m;
    g = vector < vector <int> >(n+1);
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        dm[y]++;
    }
    for(i = 1; i <= n; i++)
        adauga(s, i);
    while(s != NULL)
    {
        while(dm[s -> info] == 0)
        {
            adauga(z, s -> info);
            s = s -> urm;
        }
        while(z != NULL)
        {
            k = g[z -> info].size() - 1;
            while(k >= 0)
            {
                dm[g[z -> info][k]]--;
                k--;
            }
            fout << z -> info << " ";
            z = z -> urm;
        }
        nod * s2 = s, * sa;
        while(s2 != NULL)
        {
            if(dm[s2 -> info] == 0)
            {
                adauga(z, s2 -> info);
                sa = s2;
                s2 = s2 -> urm;
                eliminare(s, sa -> info);
            }
            else
                s2 = s2 -> urm;
        }
    }
    while(z != NULL)
    {
        k = g[z -> info].size() - 1;
        while(k >= 0)
        {
            dm[g[z -> info][k]]--;
            k--;
        }
        fout << z -> info << " ";
        z = z -> urm;
    }
}