Cod sursa(job #1651883)

Utilizator bogdandvDamaschin Bogdan-Valentin bogdandv Data 14 martie 2016 09:05:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include<fstream>
#include <vector>
#include <stack>
#include<algorithm>
using namespace std;
int n,m,i;
vector<vector<int> > graph;
vector<bool> visited;
vector<int> rezultat;
void dfs(int vertex)
{
    //cout<<vertex<<" ";
    if(vertex<0 || vertex>n-1)
        return;
    //cout<<"!2";
    stack<int> myst;
    int element;
    bool found;
    myst.push(vertex);
    visited[vertex]=true;
    while(!myst.empty())
    {
        element=myst.top();
        found=false;
        for(i=0;i<graph[element].size() && !found;i++)
            {
            if(!visited[ graph[element][i] ])
                found=true;
            }
            i--;
        if(found)
        {

            myst.push( graph[element][i] );
            visited[ graph[element][i] ]=true;
        }
        else
        {
            rezultat.push_back(myst.top());
            myst.pop();
        }
    }
}
int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    f>>n>>m;
    graph.resize(n);
    visited.resize(n,false);
    int x,y;
    for(int i=0;i<m;i++)
    {
        f>>x>>y;
        x--;
        y--;
        graph[x].push_back(y);
    }
    for(int j=0;j<n;j++)
    {
    if(!visited[j])
        {
            dfs(j);
        }
    }
    for(int j=rezultat.size()-1;j>=0;j--)
        g<<rezultat[j]+1<<" ";
    return 0;
}