Cod sursa(job #640071)

Utilizator psycho21rAbabab psycho21r Data 24 noiembrie 2011 18:21:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

struct node
{
    vector <int> neighbour;
    bool visited;
};

int main()
{

    int n, m, temp_i, temp_j;
    node node[50000];
    ifstream in("sortaret.in");
    in>>n>>m;
    for (int i = 0; i < m; ++i)
    {
        in >> temp_i >> temp_j;
        node[temp_i-1].neighbour.push_back(temp_j-1);
    }
    in.close();
    stack <int> node_stack, visited_nodes;
    for (int i = 0; i < n; ++i)
        node[i].visited = false;
    for (int i = 0; i < n; ++i)
        if(!node[i].visited)
        {
            visited_nodes.push(i);
            node[i].visited = true;
            int v = i, it;
            bool k = false;
            while(!visited_nodes.empty())
            {
                v = visited_nodes.top();
                k = false;
                for(it = 0; it < node[v].neighbour.size(); ++it)
                    if(!node[node[v].neighbour[it]].visited)
                    {
                        k = true;
                        break;
                    }
                if(!k)
                {
                    node_stack.push(visited_nodes.top());
                    visited_nodes.pop();
                }
                else
                {
                    visited_nodes.push(node[v].neighbour[it]);
                    node[node[v].neighbour[it]].visited = true;
                }
            }
        }
    ofstream out("sortaret.out");
    while(!node_stack.empty())
    {
        out << node_stack.top()+1 << " ";
        node_stack.pop();
    }
    out.close();

    return 0;
}