Cod sursa(job #1434042)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 10 mai 2015 12:20:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>

//#define pb push_back

using namespace std;

const char iname[] = "sortaret.in";
const char oname[] = "sortaret.out";
const int NMAX = 50100;

vector<int> g[NMAX];
vector<int> c[NMAX];
int q[NMAX], deg[NMAX];
int n, m;

void read()
{
    ifstream f(iname);
    f>>n>>m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        f>>x>>y;
        g[x].push_back(y);
        //c[x].push_back(cost);
        deg[y]++;
    }
}

void write()
{
    ofstream g(oname);
    for(int i = 1; i <= q[0]; i++)
        g<<q[i]<<' ';
}

void sort_topologically()
{
    vector<int> :: iterator it;
    for(int i = 1; i <= n; i++)
        if(deg[i] == 0)
            q[++q[0]] = i;
    for(int i = 1; i <= n; i++)
    {
        int x = q[i];
        for(it = g[x].begin(); it != g[x].end(); ++it)
        {
            deg[*it]--;
            if(deg[*it] == 0)
                q[++q[0]] = *it;
        }
    }
}
int main()
{
    read();
    sort_topologically();
    write();
    return 0;
}