Cod sursa(job #978040)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 27 iulie 2013 16:56:00
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<vector>
#define NMAX 5001
using namespace std;
 
ifstream f("sortaret.in");
ofstream g("sortaret.out");
 
int col[NMAX], A[NMAX][NMAX];
vector <int> sol;
int N, M;
  
void read(){
    int X, Y, i, j;
    f>>N>>M;
    for(i = 1; i <= N; i++){
        for(j = 1; j <= N; j++)
            A[i][j] = 0;
        col[i] = 0;
    }
 
    for(i = 1; i <= M; i++){
        f>>X>>Y;
        A[X][Y] = 1;
    }
}
  
void DFS(int u){
    int v;
    col[u] = 1;
 
    for(v = 1; v <= N; v++)
        if(A[u][v] == 1 && col[v] == 0)
            DFS(v);
 
    sol.push_back(u);
}
 
void print(){  
    int i;
    for(i = sol.size() - 1; i >= 0; i--)
        g<<sol[i]<<' ';
}
  
int main(){
    int i;
    read();
    for(i = 1; i <= N; i++)
        if(col[i] == 0)
            DFS(i);
 
    print();   
 
    return 0;
}