Cod sursa(job #2080121)

Utilizator MariusGeantaMarius Geanta MariusGeanta Data 2 decembrie 2017 14:33:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>

#define NMAX 50005
using namespace std;

int N, M;
vector<vector<int>> G(NMAX);
vector<int> sorted;
vector<bool> v(NMAX);

void read_data()
{
    int a, b;
    
    scanf("%d%d", &N, &M);
//    G.resize(N);
//    v.resize(N);
    
    for (int i = 0; i < M; i++)
    {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
    }
    
//    for (int i = 1; i <= N; i++)
//    {
//        printf("%d: ", i);
//        for (int j = 0; j < G[i].size(); j++)
//        {
//            printf("%d ", G[i][j]);
//        }
//        printf("\n");
//    }
}


void visit(int x)
{
//    printf("%d\n", x);
    v[x] = true;
    for (int i = 0; i < G[x].size(); i++)
    {
        if (!v[G[x][i]])
        {
            visit(G[x][i]);
        }
    }
    sorted.push_back(x);
}

void DFS()
{
    for (int i = 1; i <= N; i++)
    {
        if (!v[i])
        {
            visit(i);
        }
    }
}

void write_data()
{
    for (int i = N - 1; i >=0; i--)
    {
        printf("%d ", sorted[i]);
    }
}

int main(int argc, const char * argv[])
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    
    read_data();
    DFS();
    write_data();
    
    return 0;
}