Pagini recente » Cod sursa (job #2883820) | Cod sursa (job #1896951) | Cod sursa (job #1664692) | Cod sursa (job #1774613) | Cod sursa (job #651892)
Cod sursa(job #651892)
//Sortare topologica, facuta all OOP and stuff
//Ar trebui sa aiba un punctaj foarte scazut, dar e for teh lulz, anyways
#include <fstream>
#include <vector>
using namespace std;
class Node;
class Graf;
ostream &operator <<(ostream &out, vector<Node*> &st);
class Node {
friend class Graf;
private:
int number;
vector<Node*> neighbors;
vector<Node*>::iterator iterator;
Graf *parent;
bool started_marking;
void addNeighbor(Node *node) {neighbors.push_back(node);}
public:
Node (int number, Graf* parent):number(number), parent(parent), started_marking(false) {}
Node *getNextNeighbor();
int getNumber()const{return number;}
};
class Graf {
friend class Node;
private:
vector<bool> visited;
vector<Node*> nodes;
void dfs(Node *node);
vector<Node*> topology;
public:
Graf(int n);
~Graf();
void addEdge(int x, int y);
void computeTopology();
void printTopology(ostream& out) {out << topology;}
friend istream &operator >>(istream &in, Graf *&gr);
};
Node *Node::getNextNeighbor()
{
if (!started_marking) {
iterator = neighbors.begin();
started_marking = true;
}
while (true) {
if (iterator == neighbors.end()) {
started_marking = false;
return 0;
}
Node *ret = *iterator;
++iterator;
if (!parent->visited[ret->number])
return ret;
}
return 0;
}
Graf::Graf(int n)
{
visited.reserve(n);
fill(visited.begin(), visited.begin() + n, false);
for (int i = 0; i<n; ++i) {
nodes.push_back(new Node(i, this));
}
}
Graf::~Graf()
{
for (unsigned i = 0; i<nodes.size(); ++i)
delete nodes[i];
}
void Graf::addEdge(int x, int y)
{
nodes[x]->addNeighbor(nodes[y]);
}
void Graf::computeTopology()
{
if (!topology.empty()){
return;
}
for (vector<Node*>::iterator it = nodes.begin(); it != nodes.end(); ++it)
if (!visited[(*it)->number]) {
dfs(*it);
}
}
void Graf::dfs(Node *node)
{
Node *vec;
visited[node->number] = true;
while ( (vec = node->getNextNeighbor()) != 0 )
dfs(vec);
topology.push_back(node);
}
istream &operator >>(istream &in, Graf *&gr)
{
int n, m;
in >> n >> m;
gr = new Graf(n);
int x, y;
for (int i = 0; i<m; ++i) {
in >> x >> y;
gr->addEdge(x-1,y-1);
}
return in;
}
ostream &operator <<(ostream &out, vector<Node*> &st)
{
while (!st.empty()) {
out << st.back()->getNumber() + 1 << " ";
st.pop_back();
}
return out;
}
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
Graf *g;
fin >> g;
fin.close();
g->computeTopology();
g->printTopology(fout);
fout << endl;
fout.close();
delete g;
return 0;
}