Cod sursa(job #1636629)

Utilizator AnaMariaPintilieAna Maria Pintilie AnaMariaPintilie Data 7 martie 2016 11:13:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
int N,M;
vector < vector <int> > graph;
vector<bool>visited;
stack<int>sortare;

void DFS(int vertex)
{
    if(vertex<0 || vertex>N-1)
        return;
    stack<int>s;
    int element,i;
    bool found;
    s.push(vertex);
    visited[vertex]=true;
    while(!s.empty())
    { element=s.top();
    found=false;
    for(i=0;i<graph[element].size() && !found;i++)
        if(!visited[graph[element][i]])
             found=true;
    if(found) {i--;
                s.push(graph[element][i]);
                visited[graph[element][i]]=true;
                }
    else {sortare.push(s.top());
          s.pop();}
}}

int main()
{
    int x,y,i;
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    fin>>N>>M;
    graph.resize(N);
    visited.resize(N,0);
    for(i=0;i<M;i++)
    {
        fin>>x>>y;
        x--;y--;
        graph[x].push_back(y);
    }


    for(i=0;i<visited.size();i++)
        if(!visited[i]) DFS(i);

    for(i=0;i<visited.size();i++)
    {
        fout<<sortare.top()+1<<" ";
        sortare.pop();
    }
    fin.close();
    fout.close();
    return 0;
}