Cod sursa(job #2202842)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 10 mai 2018 08:54:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <queue>
#include <list>

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

struct lista{
    list<int> urm;
    list<int> ant;
}v[50005];

queue<int> q;
list<int>::iterator it, it2;

int main()
{
    int  i, M, N, x, y;

    fin >> N >> M;

    for( i = 1; i <= M; i++) fin >> x >> y,
        v[x].urm.push_back(y), v[y].ant.push_back(x);

    for( i = 1; i <= N; i++)
        if(v[i].ant.empty())
        q.push(i), fout << i << " ";

    while(!q.empty())
    {
        x = q.front(), q.pop();
        for(it = v[x].urm.begin(); it != v[x].urm.end(); it++)
        {
            y = *it;it++;
            for(it2 = it; it2 != v[x].urm.end(); it2++)
                if( *it2 == y ) it2 = v[x].urm.erase(it2),it2--;it--;

            for(it2 = v[y].ant.begin(); it2 != v[y].ant.end(); it2++)
                if( *it2 == x ) it2 = v[y].ant.erase(it2),it2--;
            if(v[y].ant.empty())
                q.push(y), fout << y << " ";
        }
    }

    return 0;
}