Cod sursa(job #1757783)

Utilizator CatalinOlaruCatalin Olaru CatalinOlaru Data 15 septembrie 2016 20:37:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
vector<vector<int> > graf;

stack<int> stiva;
int* visited;
void topsort(int node)
{
    //cout<<"toposrot for node "<<node<<endl;
    for(int i=0;i<graf[node].size();i++)
    {
        if(visited[graf[node][i]]==0)
            topsort(graf[node][i]);
    }
    stiva.push(node);
    visited[node]=1;
}


int main()
{
    fstream f,g;
    f.open("sortaret.in",ios::in);
    g.open("sortaret.out",ios::out);
    int N=0,M=0;
    f>>N>>M;

    visited=new int[N+1];
    for(int i=0;i<=N;i++)
        visited[i]=0;
    for(int i=0;i<=N;i++)
    {
        vector<int> l;
        graf.push_back(l);
    }
    int x,y;
    for(int i=0;i<M;i++)
    {
        f>>x>>y;
        graf[x].push_back(y);
    }

    for(int i=1;i<graf.size();i++)
    {
        if(visited[i]==0)
            topsort(i);
    }
    while(!stiva.empty())
    {
        g<<stiva.top()<<" ";stiva.pop();
    }

    f.close();g.close();
}