Cod sursa(job #1706630)

Utilizator PetruDPetru Dimitriu PetruD Data 22 mai 2016 22:03:59
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;

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

struct Digraf
{
    int n;
    vector<int> a[5000];
    int* np;

    Digraf(int n)
    {
        this->n=n;
        np = new int[n];

        for (int i=0;i<n;i++)
        {
            np[i] = 0;
        }
    }

    void add(int src, int dst)
    {
        a[src].push_back(dst);
        np[dst]++;
    }
};

void sortareTopologica(Digraf &D)
{
    queue<int> C;
    int u;
    for (u = 0; u<D.n; u++)
        if (D.np[u] == 0)
            C.push(u);
    for (int k = 0; k<D.n; k++)
    {
        int v;
        if (C.empty())
            cout << "Graf cu cicluri!", exit(1);
        u = C.front();
        C.pop();
        out << u << "\n";
        //L.push_back(u);
        //cout << D.a[u].size() << " ";
        for (int i=0;i<D.a[u].size();i++)
        {
            v = D.a[u][i];
            D.np[v]--;
            //cout << v << "!" << D.np[v] << "--\n";
            if (D.np[v]==0)
                C.push(v);
        }
    }
}

int main()
{
    int x = -1, y = 0;
    int n;
    in >> n;
    Digraf digraf(n);
    in >> x >> y;
    while (x!=0 || y!=0)
    {
        digraf.add(x,y);
        in >> x >> y;
    };
    out << "\n";
    sortareTopologica(digraf);
}