Cod sursa(job #639967)

Utilizator psycho21rAbabab psycho21r Data 24 noiembrie 2011 14:25:39
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 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;

    //cout << 0;
    stack <int> node_stack;
    for (int iterator = 0; iterator < n; ++iterator)
        if(!visited[iterator])
        {
            visited_nodes.push(iterator);
            int v = iterator, i;
            visited[iterator] = 1;
            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()+1 << " ";
        node_stack.pop();
    }

    return 0;
}