Cod sursa(job #726959)

Utilizator algotrollNume Fals algotroll Data 27 martie 2012 17:34:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<vector>
#define _NM 50010
using namespace std;

int nN, nM;
vector<int> vAd[_NM]; //graf transpus

void dfs(int nod, vector<int> &sol)
{
	static bool viz[_NM];
	viz[nod]=1;
	for (vector<int>::iterator it=vAd[nod].begin();it!=vAd[nod].end();++it)
		if (!viz[*it]) dfs(*it,sol);
	sol.push_back(nod);
}

int main()
{
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	fin>>nN>>nM;
	static int in_cnt[_NM];
	for (int i=1;i<=nM;i++)
	{
		int nod1,nod2;
		fin>>nod1>>nod2;
		vAd[nod2].push_back(nod1);
		in_cnt[nod1]++;
	}
	vector<int> sol;
	for (int i=1;i<=nN;i++)
		if (in_cnt[i]==0) dfs(i,sol);
	for (int i=0;i<sol.size();i++)
		fout<<sol[i]<<' ';
	return 0;
}