Cod sursa(job #1443504)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 28 mai 2015 00:26:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <cstdio>
#include <cassert>
#include <vector>
#include <list>
#include <set>
#include <stack>
using namespace std;
#define _submit
#ifdef _submit
#define InFile "sortaret.in"
#define OutFile "sortaret.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned short ushort;

class graph {
private:
	vector < list<int> > reverse;
	vector < list< pair<int, list<int>::iterator> > > adiacence;
public:
	graph();
	graph(int);
	graph(graph*);
	void resize(int newSize);
	void newMuchie(int, int);
	void removeDuplicates();
	list< pair<int, list<int>::iterator> >::iterator removeMuchie(list< pair<int, list<int>::iterator> >&, list< pair<int, list<int>::iterator> >::iterator&);
	int size();
	list<int> topsort();
	friend int main();
};

graph::graph() {
	reverse.reserve(10000);
	adiacence.reserve(10000);
}

graph::graph(int n) {
	reverse.resize(n);
	adiacence.resize(n);
}

graph::graph(graph *G) {
	reverse = G->reverse;
	adiacence = G->adiacence;
}

void graph::resize(int newSize) {
	reverse.resize(newSize);
	adiacence.resize(newSize);
}

void graph::newMuchie(int n1, int n2) {
	swap(n1, n2);
	reverse[n1].push_back(n2);
	list<int>::iterator muc = reverse[n1].end();
	muc--;
	pair<int, list<int>::iterator> p = { n1, muc };
	adiacence[n2].push_back(p);
}

int graph::size() {
	return reverse.size();
}

list< pair<int, list<int>::iterator> >::iterator graph::removeMuchie(list< pair<int, list<int>::iterator> >& L, list< pair<int, list<int>::iterator> >::iterator& nod) {
	int nod2 = nod->first;
	list<int>::iterator it = nod->second;
	reverse[nod2].erase(it);
	auto toret = L.erase(nod);
	return toret;
}

list<int> graph::topsort() {
	list<int> L;
	stack<int> S;
	for (int i = 0; i<this->size(); ++i)
	if (this->reverse[i].empty())
		S.push(i);
	while (!S.empty()) {
		int nod = S.top();
		S.pop();
		L.push_back(nod);
		for (auto i = this->adiacence[nod].begin(); i != this->adiacence[nod].end();) {
			int nd2 = i->first;
			i = this->removeMuchie(adiacence[nod], i);
			if (reverse[nd2].empty())
				S.push(nd2);
		}
	}
	return L;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	int N, M;
	scanf("%d%d", &N, &M);
	graph *G = new graph(N);
	for (int i = 0; i < M; i++) {
		int X, Y;
		scanf("%d%d", &X, &Y);
		G->newMuchie(X - 1, Y - 1);
	}
	list<int> L = G->topsort();
	for (auto i = L.begin(); i != L.end(); i++)
		printf("%d ", (*i) + 1);
	printf("\n");
	return 0;
}