Pagini recente » Cod sursa (job #47731) | Cod sursa (job #1575099) | Cod sursa (job #271229) | Cod sursa (job #2646468) | Cod sursa (job #1443500)
#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", &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.rbegin(); i != L.rend(); i++)
printf("%d ", (*i) + 1);
printf("\n");
return 0;
}