Cod sursa(job #1514878)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 31 octombrie 2015 19:20:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 50000 + 1;
const int MAX_M = 100000 + 1;
const int NIL = -1;

struct Edge
{
    int v;
    int urm;
};

Edge G[MAX_M];
int head[MAX_N];
bool visited[MAX_N];
int lista[MAX_N];

int N, M;
int contor = 0;
int dim;

void add_edge(int x, int y)
{
    G[contor] = {y, head[x]};
    head[x] = contor++;
}

void dfs(int nod)
{
    visited[nod] = true;

    for (int p = head[nod]; p != NIL; p = G[p].urm)
    {
        int v = G[p].v;

        if (!visited[v])
            dfs(v);
    }

    lista[ ++dim ] = nod;
}

int main()
{
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");

    in >> N >> M;

    for (int i = 1; i <= N; ++i)
        head[i] = NIL;

    for (int i = 1; i <= M; ++i)
    {
        int a, b;
        in >> a >> b;

        add_edge(a, b);
    }

    for (int i = 1; i <= N; ++i)
        if (!visited[i])
            dfs(i);

    for (int i = N; i >= 1; i--)
        out << lista[i] << " ";

    return 0;
}