Pagini recente » Cod sursa (job #2768104) | Cod sursa (job #2643914) | Cod sursa (job #2966958) | rf_3 | Cod sursa (job #3165518)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int MAX_NODES = 20000;
vector<int> graph[MAX_NODES + 1];
bitset<MAX_NODES + 1> fr;
int sortedNodes[MAX_NODES + 1][MAX_NODES + 1];
int sortedNodesLen;
void topologicalSort(int &sortedNodesLen, int sortedNodes[MAX_NODES + 1][MAX_NODES + 1], int startNode, int line) {
for (vector<int>::iterator it = graph[startNode].begin(); it < graph[startNode].end(); ++it) {
if (fr[*it] == 0) {
sortedNodes[line][++sortedNodesLen] = *it;
fr[*it] = 1;
topologicalSort(sortedNodesLen, sortedNodes, *it, line);
}
}
}
int main() {
int noNodes, noEdges;
fin >> noNodes >> noEdges;
for (int i = 1; i <= noEdges; ++i) {
int start, end;
fin >> start >> end;
graph[start].push_back(end);
}
int line = 1;
for (int i = 1; i <= noNodes; ++i) {
if (graph[i].size() == 0) {
sortedNodes[line][++sortedNodesLen] = i;
fr[i] = 1;
}
}
for (int i = 1; i <= noNodes; ++i) {
if (fr[i] == 0) {
++line;
sortedNodesLen = 0;
sortedNodes[line][++sortedNodesLen] = i;
fr[i] = 1;
topologicalSort(sortedNodesLen, sortedNodes, i, line);
}
}
for (int i = line; i >= 1; --i) {
for (int j = 1; sortedNodes[i][j] != 0; ++j) {
fout << sortedNodes[i][j] << ' ';
}
}
return 0;
}
/*
9 8
1 2
1 3
3 4
3 5
5 9
4 6
4 7
4 8
=>
1 2 3 4 5 6 7 8 9
4 3
1 2
3 2
4 1
=>
4 3 1 2
*/