Cod sursa(job #762115)

Utilizator vitaleamaldur vitalik vitalea Data 28 iunie 2012 18:33:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdio>
#include <queue>

#define ALB 0
#define GRI 1
#define NEGRU 2

std::vector<int> c;
std::vector< std::vector<int> > g;
std::deque<int> r;

void explorare( int nod )
{
    c[nod] = GRI;
    for( int i = 0; i < g[nod].size(); i++ )
    {
        if( c[ g[nod][i] ] == ALB )
        {
            explorare( g[nod][i] );
        }
    }
    c[nod] = NEGRU;
    r.push_front( nod );
}

void dfs()
{
    c.resize( g.size() + 1 );

    for( int i = 1; i <= g.size(); i++ )
    {
        c[i] = ALB;
    }

    for( int i = 1; i < g.size(); i++ )
    {
        if( c[i] == ALB )
            explorare( i );
    }

}

void print()
{
    for( int i = 1; i < g.size(); i++ )
    {
        std::cout << "nod " << i << "vecini ";
        for( int j = 0; j<g[i].size(); j++ )
        {
            std::cout << g[i][j] << " ";
        }
        std::cout << "\n";
    }
}

int main()
{
    std::ifstream in ("sortaret.in");
    std::ofstream out("sortaret.out");
    int n, m;
    in >> n >> m;
    g.resize( n + 1 );
    for( int i = 0; i < m; i++ )
    {
        int x, y;
        in >> x >> y;
        g[x].push_back( y );
    }
    dfs();
    for( int i = 0; i < r.size(); i++ )
        out << r[i] << ' ';
    in.close();
    out.close();
    return 0;
}