Cod sursa(job #650831)

Utilizator informatician28Andrei Dinu informatician28 Data 18 decembrie 2011 23:50:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream> 
#include<vector> 

#define MAXN 50001 

using namespace std; 

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

int N,M,deg[MAXN],Q[MAXN]; 
vector<int>G[MAXN];

void solve() 
{
	int i,x; 
	vector<int>::iterator it;
	
	for(i=1;i<=N;i++) 
		if(deg[i]==0) Q[++Q[0]]=i; 
	
	for(i=1;i<=N;i++) 
	{
		x=Q[i]; 
		
		for(it=G[x].begin(); it!=G[x].end(); it++)
		{
			deg[*it]--; 
			if(deg[*it]==0) 
				Q[++Q[0]]=*it; 
		}
	}
}

void read_data() 
{
	int i,x,y;
	in >> N >> M; 
	for(i = 1; i <= M; i++) 
		{
			in >> x >> y; 
	G[x].push_back(y); deg[y]++; 
	}
}
	
void write_data() 
{
	int i; 
	for(i=1;i<=N;i++) 
		out<<Q[i]<<" "; 
}
	
int main() 
{
	read_data(); 
	solve();
	write_data(); 
}