Cod sursa(job #866508)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 28 ianuarie 2013 11:22:05
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector <int> G[50010];
bool viz[50010];
int p[50010], np;

inline void Read()
{
    ifstream f("sortaret.in");
    f>>n>>m;
    int i, x, y;
    for (i=1; i<=m; i++)
    {
        f>>x>>y;
        G[x].push_back(y);
    }
    f.close();
}

inline void DFS (int x)
{
    viz[x] = true;
    vector <int>::iterator it, final;
    for (it = G[x].begin(), final = G[x].end(); it!=final; it++)
    {
        if (viz[*it] == false)
            DFS(*it);
    }
    p[++np] = x;
}

inline void Solve()
{
    int i;
    for (i=1; i<=n; i++)
        if (viz[i] == false)
            DFS(i);
}

inline void Write()
{
    ofstream g ("sortaret.out");
    int i;
    for (i=n; i; i--)
        g<<p[i]<<" ";
    g<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}