Cod sursa(job #2445906)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 5 august 2019 22:51:29
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;

class graphTopologicalSort
{
private:
#define uint unsigned int
#define pb push_back
#define G_TOPOLOGICAL_SORT_CHECK_CREATED(ret) if (!created) return ret
#define G_TOPOLOGICAL_SORT_CIRCUIT 2
#define G_TOPOLOGICAL_SORT_OK 1
#define G_TOPOLOGICAL_SORT_ERROR 3
    bool created;
    std::vector<uint>*g;
    uint *di, *dc, n;
public:
    graphTopologicalSort(): g(nullptr), di(nullptr), dc(nullptr), created(false){}
    bool create(uint sz)
    {
        if (created) return false;
        g = new std::vector<uint>[sz + 2];
        if (g == nullptr) return false;
        di = new uint[sz + 2];
        if (di == nullptr)
        {
            delete[] g;
            return false;
        }
        dc = new uint[sz + 2];
        if (dc == nullptr)
        {
            delete[] g;
            delete[] di;
            return false;
        }
        n = sz;
        for (uint i=0;i<sz + 2;++i)
            di[i] = dc[i] = 0;
        created = true;
        return true;
    }
    bool addEdge(uint x, uint y)
    {
        G_TOPOLOGICAL_SORT_CHECK_CREATED(false);
        if (x > n || y > n) return false;
        g[x].pb(y);
        ++di[y];
        return true;
    }
    uint topologicalSort(std::vector<uint> &top)
    {
        G_TOPOLOGICAL_SORT_CHECK_CREATED(G_TOPOLOGICAL_SORT_ERROR);
        top.clear();
        std::queue<uint>q;
        for (uint i=1;i<=n;++i)
        {
            dc[i] = di[i];
            if (!dc[i])
                q.push(i);
        }
        uint nodes = 0, act;
        while (!q.empty())
        {
            act = q.front();
            ++nodes;
            top.pb(act);
            q.pop();
            for (uint i=0;i<g[act].size();++i)
            {
                --dc[g[act][i]];
                if (!dc[g[act][i]])
                    q.push(g[act][i]);
            }
        }
        if (nodes < n) return G_TOPOLOGICAL_SORT_CIRCUIT;
        return G_TOPOLOGICAL_SORT_OK;
    }
};

int main()
{
    int n, m, x, y;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d %d",&n,&m);
    graphTopologicalSort topp;
    topp.create(n);
    for (int i=1;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        topp.addEdge(x, y);
    }
    vector<unsigned int>ans;
    topp.topologicalSort(ans);
    for (auto x:ans)
        printf("%d ", x);
    printf("\n");
    return 0;
}