Cod sursa(job #1846970)

Utilizator danyvsDan Castan danyvs Data 14 ianuarie 2017 10:49:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 50001;

int n, m;
vector < vector < int > > graph(NMAX);
int gr_int[NMAX];
bool seen[NMAX];

void read()
{
    int i, x, y;
    fin >> n >> m;
    for (i = 1; i <= m; ++ i)
        {
         fin >> x >> y;
         graph[x].push_back(y);
         ++ gr_int[y];
        }
}

void topological_sort()
{
    int i;
    bool ok;
    vector < int > temp;
    vector < int > :: iterator it, itt;
    ok = false;
    while (!ok)
        {
         ok = true;
         for (i = 1; i <= n; ++ i)
            if (!gr_int[i] && !seen[i])
                {
                 temp.push_back(i);
                 seen[i] = true;
                 ok = false;
                }
         for(it = temp.begin(); it != temp.end(); ++ it)
            {
             fout << *it << " ";
             for (itt = graph[*it].begin(); itt != graph[*it].end(); ++ itt)
                {
                 -- gr_int[*itt];
                 graph[*it].erase(itt);
                 -- itt;
                }
            }
         temp.erase(temp.begin(), temp.end());
        }
    fout << "\n";
}

int main()
{
    read();
    fin.close();
    topological_sort();
    fout.close();
    return 0;
}