Cod sursa(job #953642)

Utilizator ioanapopaPopa Ioana ioanapopa Data 26 mai 2013 21:35:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<iostream>
#include<vector>
#include<fstream>
using namespace std;

class graf
{
	int n,m;
	vector<vector<int> > v;
	vector<int> viz;
	vector<int> sortat;
	typedef vector<int>:: iterator it;
public:
	graf()
	{}
	void create()
	{
		ifstream f("sortaret.in");
		ofstream g("sortaret.out");
		int a,b;
		f>>n>>m;
		v.resize(n+2);
		viz.resize(n+2);
		for(int i=1;i<=n+1;i++)
				viz[i]=0;
		for(int i=0;i<m;i++)
			{
				f>>a>>b;
				v[a].push_back(b);
			}
		for(int i=1;i<=n;i++)
			df(i);
		for(int i= n-1;i>=0;i--)
			g<<sortat[i]<<" ";
				
	}

	void df(int x)
	{
		if(!viz[x])
		{
			viz[x]=1;
			vector<int> &aux = v[x];
			for(it iterator=aux.begin(); iterator!= aux.end();++iterator)
			{
				if(!viz[*iterator]) 
					df(*iterator);
			}
			sortat.push_back(x);
		}	
	}
};
int main()
{
	graf G;
	G.create();
	return 0;
}