Pagini recente » Cod sursa (job #1918075) | Cod sursa (job #1350616) | Cod sursa (job #1883510) | Cod sursa (job #1890017) | Cod sursa (job #1560908)
#include <vector>
#include <fstream>
#include <iostream>
#include <set>
using namespace std;
int N, M;
set<int> initialNodes;
struct Node {
int val;
int edges;
vector<int> nextNodes;
Node(int val) {
this->val = val;
this->edges = 0;
}
void pushNext(int n) {
nextNodes.push_back(n);
}
void incEdges() {
this->edges++;
}
void decEdges() {
this->edges--;
if(this->edges == 0) {
initialNodes.insert(this->val);
}
}
};
/*
int beginningNode(vector<Node>& nodes) {
int e = -1;
int i = 1;
while(e != 0) {
e = nodes[i].edges;
i++;
}
return i-1;
}
ostream& operator<< (ostream& o, const Node& node) {
o << "(" << node.edges << ", [";
vector<int> list = node.nextNodes;
for(int i = 0; i < list.size(); i++) {
o << list[i] << " ";
}
return o << "])";
}
*/
int main() {
ifstream in("sortaret.in");
ofstream out("sortaret.out");
in >> N >> M;
int fst;
int snd;
vector<Node> nodes;
for(int i = 0; i <= N; i++) {
if(i != 0) {
initialNodes.insert(i);
}
Node node(i);
nodes.push_back(node);
}
for(int i = 0; i < M; i++) {
in >> fst >> snd;
nodes[fst].pushNext(snd);
nodes[snd].incEdges();
initialNodes.erase(snd);
}
for(int i = 0; i < N; i++) {
vector<int> decEdgeNodes;
for (set<int>::iterator it=initialNodes.begin(); it!=initialNodes.end(); ++it) {
int curr = *it;
// initialNodes.erase(curr);
out << curr << " ";
vector<int> nexts = nodes[curr].nextNodes;
for(int x : nexts) {
decEdgeNodes.push_back(x);
}
}
initialNodes.clear();
for(int x : decEdgeNodes) {
nodes[x].decEdges();
}
}
in.close();
out.close();
return 0;
}