Cod sursa(job #639964)

Utilizator psycho21rAbabab psycho21r Data 24 noiembrie 2011 14:09:51
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

int main()
{
    int graph[500][500], n, m, temp_i, temp_j;
    ifstream in("sortaret.in");
    in>>n>>m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            graph[i][j] = 0;
    for (int i = 0; i < m; ++i)
    {
        in >> temp_i >> temp_j;
        graph[temp_i-1][temp_j-1] = 1;
    }
    in.close();

    /*--------------------------------------------*/

    stack <int> visited_nodes;
    bool visited[500];
    for (int i = 0; i < n; ++i)
        visited[i] = false;

    visited_nodes.push(0);
    //cout << 0;
    visited[0] = true;
    int v = 0, i;
    //cout << char(65) << " ";
    stack <int> node_stack;
    while(!visited_nodes.empty())
    {
        v = visited_nodes.top();
        //cout << char (v+65) << " ";
        i = 0;
        bool k = false;
        while(i<n)
        {
            if(graph[v][i]&&!visited[i])
            {
                k = true;
                break;
            }
            i++;
        }
        if(!k)
        {
            node_stack.push(visited_nodes.top());
            visited_nodes.pop();
        }
        else
        {
            visited_nodes.push(i);
            visited[i] = true;
        }
    }

    ofstream out("sortaret.out");
    while(!node_stack.empty())
    {
        out << node_stack.top() << " ";
        node_stack.pop();
    }

    return 0;
}