Cod sursa(job #1807858)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 16 noiembrie 2016 23:04:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>


using namespace std;

void dfs(vector<int> *arcs, int current, int *visited, stack<int> &myStack)
{
    for (vector<int>::iterator it = arcs[current].begin(); it != arcs[current].end(); ++it)
    {
        int next = *it;
        //cout << 2;
        if (visited[next] == 0)
        {
            visited[next] = 1;
            dfs(arcs, next, visited, myStack);
        }
    }

    myStack.push(current+1);
}

int main()
{
    ifstream cin ("sortaret.in");
    ofstream cout ("sortaret.out");
    //
    int n, m;
    cin >> n >> m;

    vector<int> arcs[n];
    stack<int> myStack;
    int visited[n];
    int in_deg[n];
    for (int i = 0; i < n; ++i)
        visited[i] = 0,
        in_deg[i] = 0;

    int x, y;
    for (int i = 0; i < m; ++i)
    {
        cin >> x >> y;
        ++in_deg[y-1];
        arcs[x-1].push_back(y-1);
    }

    for (int i = 0; i < n; ++i)
    {
        if (visited[i] == 0 && in_deg[i] == 0)
        {
            visited[i] = 1;
            dfs(arcs, i, visited, myStack);
        }
    }
    while (!myStack.empty())
    {
        int top = myStack.top();
        cout << top << " ";
        myStack.pop();
    }
    /*
    for (int i = 0; i < m; ++i)
    {
        cout << i << ": ";
        for (vector<int>::iterator it = arcs[i].begin(); it != arcs[i].end(); ++it)
            cout << *it << " ";

        cout << "\n";
    }*/


    return 0;
}