Cod sursa(job #2168594)

Utilizator ListenerRavasz Tamas Listener Data 14 martie 2018 11:41:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
/*
struct graf
{
    int kezd, veg;
};


int n, m;
graf x[100001];
bool nod[50001];
int er[50001];
int k = 0;

void dfs(int node)
{

    for(int i = 0 ; i < m; ++i)
    {
        if(x[i].kezd == node)
        {
            if(nod[x[i].veg] == 0)
            {
                dfs(x[i].veg);
            }
        }
    }
    //cout << node << endl;
    nod[node] = 1;
    er[k++] = node;
}

void topologicalsort()
{
    for(int i = 1 ; i <= n; ++i)
    {
        if(nod[i] == 0)
            dfs(i);
    }
}
*/

const int MAXN = 50001;
int n, m;
vector<int> v[MAXN];
vector<int> q;
bool vis[MAXN];

void dfs(int k)
{
    vis[k] = 1;
    for(int i = 0 ; i < v[k].size(); ++i)
    {
        if(vis[v[k][i]] == 0)
            dfs(v[k][i]);
    }
    q.push_back(k);
}

int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    /*fin >> n >> m;



    for(int i = 0; i < m; ++i)
    {
        fin >> x[i].kezd >> x[i].veg;
    }

    topologicalsort();

    for(int i = k-1 ; i >= 0; --i)
    {
        fout << er[i] << " ";
    }*/

    fin >> n >> m;
    for(int i = 0; i <= m; ++i)
    {
        int a, b;
        fin >> a >> b;
        v[a].push_back(b);
    }

    for(int i = 1 ; i <= n; ++i)
    {
        if(vis[i] == 0)
            dfs(i);
    }

    for(int i = q.size() - 1;  i >= 0; --i)
    {
        fout << q[i] << " ";
    }

    return 0;
}