Cod sursa(job #1274726)

Utilizator HotSteelBeteag Ion Andrei HotSteel Data 24 noiembrie 2014 10:56:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>

#include <vector>

using namespace std;

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    int V,E;
    scanf("%d%d", &V, &E);

    vector < vector < int > > M (V + 1);
    vector < int > EdgesCount(V + 1);

    int i, j;
    int VA, VB;

    for(i = 1 ; i <= E ; ++i)
    {
        scanf("%d%d", &VA, &VB);
        M[VA].push_back(VB);
        EdgesCount[VB] ++;
    }

    vector < int > IsolatedVertices;
    IsolatedVertices.reserve(V + 1);
    vector < int > :: iterator it, it2;

    for(i = 1 ; i <= V ; ++i)
        if(EdgesCount[i] == 0)
            IsolatedVertices.push_back(i);

    int Vertice;

    for(it = IsolatedVertices.begin() ; it != IsolatedVertices.end() ; ++it)
    {
        Vertice = *it;
        for(it2 = M[Vertice].begin() ; it2 != M[Vertice].end() ; ++it2)
        {
            EdgesCount[*it2] --;
            if(EdgesCount[*it2] == 0)
                    IsolatedVertices.push_back(*it2);
        }
    }

    for(it = IsolatedVertices.begin() ; it != IsolatedVertices.end() ; ++it)
    {
        printf("%d ", *it);
    }

    return 0;
}