Cod sursa(job #1240210)

Utilizator yellowstarTraian Mihai yellowstar Data 10 octombrie 2014 18:33:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
//
//  main.cpp
//  sortaret
//
//  Created by Hai Tran Bach on 10/10/14.
//  Copyright (c) 2014 Hai Tran Bach. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define MAX 50000

ifstream in("sortaret.in");
ofstream out("sortaret.out");

int N,M;
vector<int> m[MAX+1];
int viz[MAX+1], sol[MAX+1];

void read();

void print();

void dfs();

void sortaret();

int main() {

    read();
    sortaret();
    print();
    
    return 0;
}

void read() {
    int i,j;
    
    in >> N >> M;
    
    for (; M; --M) {
        in >> i >> j;
        m[j].push_back(i);
    }
        
}

void print() {
    for (int i = 1; i <= N; ++i) {
        out << sol[i] << " ";
    }
    out << "\n";
}

void dfs(int i) {
    if (!viz[i]) {
        viz[i] = 1;
        for (vector<int>::iterator j = m[i].begin(); j != m[i].end(); ++j ) {
            dfs(*j);
        }
        sol[++sol[0]] = i;
    }
        
}

void sortaret() {
    for (int i = 1; i <= N; ++i) {
        dfs(i);
    }
}