Cod sursa(job #1706729)

Utilizator Cristi.96Ion Alexandru Cristian Cristi.96 Data 23 mai 2016 07:48:31
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;

vector<int> *graf = new vector<int>[100005];
int visit[100];
stack<int> sortare;

void explorare(int nod) {

    visit[nod] = -1;
    unsigned int i;
    int index;
    for ( i = 0; i < graf[nod].size(); i++)
    {
      int copil = graf[nod][i];
        if ( visit[copil] == 0)
            explorare(copil);

    }
    visit[nod] = 1;
    sortare.push(nod);

}


void solve(int n) {
    for (int i = 1; i <= n; i++)
    {
        if (visit[i] == 0)
            explorare(i);
    }
}

int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int n, m;
    f >> n >> m;
    int i;
    int x, y;

    for(i = 0; i < m; i++)
    {
        f >> x >> y;
        graf[x].push_back(y);
    }
    solve(n);
    while(!sortare.empty())
    {
        g<<sortare.top()<<" ";
        sortare.pop();
    }
}