Cod sursa(job #1153175)

Utilizator nickulNic Kul nickul Data 25 martie 2014 12:02:47
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#include<vector>

using namespace std;

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

bool lg(vector< vector<int> > a, int i)
{
	bool ok=1;
	int j;
	for(j=0;j<a.size();j++) if(a.at(i).at(j)) ok=0;
	return ok;
}

int main()
{
	int n,m,i,j;
	in>>n>>m;
	vector< vector<int> > a;
	vector<int> s,b;
	a.resize(n);
	b.resize(n);
	for(i=0;i<n;i++) 
	{
		a.at(i).resize(n);
		b.at(i)=i;
	}
	while(m--)
	{
		in>>i>>j;
		a.at(i-1).at(j-1)=1;
	}
	while(b.size())
	{
		for(i=0;i<b.size();i++) 
			if(lg(a,b.at(i))) 
			{
				s.push_back(b.at(i));
				for(j=0;j<n;j++) a.at(j).at(b.at(i))=0;
				b.erase(b.begin()+i,b.begin()+i+1);
			}
	}
	for(i=s.size();i>0;i--) out<<s.at(i-1)+1<<" ";
}