Cod sursa(job #1807852)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 16 noiembrie 2016 22:58:53
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;
ofstream out ("sortaret.out");

void dfs(vector<int> *arcs, int current, int *visited)
{

    out << current+1 << " ";
    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);
        }
    }
}

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

    vector<int> arcs[n];
    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);
        }
    }
    /*
    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;
}