Cod sursa(job #978050)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 27 iulie 2013 17:15:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<vector>
#define NMAX 50001
using namespace std;
 
ifstream f("sortaret.in");
ofstream g("sortaret.out");

struct Node{
	int nd;
	Node *next;
};
 
struct Node *L[NMAX];
int col[NMAX];
vector <int> sol;
int N, M;
  
void read(){
    int X, Y, i, j;
	struct Node *p;	
    f>>N>>M;
	for(i = 1; i <= N; i++)
		col[i] = 0;

    for(i = 1; i <= M; i++){
        f>>X>>Y;
        p=new Node;
		p->nd = Y;
		p->next = L[X];
		L[X] = p;	
    }
}
  
void DFS(int u){
    int v;
    col[u] = 1; 
   struct Node *p;
	p = L[u];
	while(p != NULL){ 
		if(col[p->nd] == 0)
			DFS(p->nd);
		p = p->next;
	}
 
    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;
}