Cod sursa(job #1220543)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 17 august 2014 16:59:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

//constants
#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define MAX 50003

//input/output files
ifstream f(FIN);
ofstream g(FOUT);

int n,m; //number of edges and vertices
vector<int> v[MAX]; //graph
int s[MAX]; //checks if the vertex was visited
vector<int> solution;

int read()
{
    f >> n;
    f >> m;

    int x,y;
    for(int i=1;i<=m;i++)
    {
        f >> x;
        f >> y;
        v[x].push_back(y);

    }

    return 0;
}

void dfs(int vertex)
{

    s[vertex] = 1;
    for(vector<int>::iterator it = v[vertex].begin(); it != v[vertex].end(); it++)
    {
        if(s[*it] != 1)
        {
            dfs(*it);
        }
    }

    solution.push_back(vertex);

}

int solve()
{
    //DFS
    for(int i=1;i<=n;i++)
    {
        if(s[i] != 1)
        {
            dfs(i);
        }
    }
    return 0;
}

int write()
{
    for(vector<int>::reverse_iterator it = solution.rbegin(); it != solution.rend(); it ++)
    {
        g << *it << " " ;
    }
    return 0;
}

int main()
{
    read();
    solve();
    write();

    return 0;
}