Pagini recente » Cod sursa (job #134724) | Cod sursa (job #556950) | Cod sursa (job #1599466) | Cod sursa (job #1065336) | Cod sursa (job #2423730)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
void topologicalSort(stack<int>* sol, bool** graph, bool* visited, int currentNode, int size);
int main() {
int n;
int m;
fin >> n;
fin >> m;
bool* visited = (bool*)malloc(sizeof(bool) * n);
for (int i = 0; i < n; ++i) {
visited[i] = false;
}
bool** graph = (bool**)malloc(sizeof(bool*) * n);
for (int i = 0; i < n; ++i) {
graph[i] = (bool*)malloc(sizeof(bool) * n);
for (int j = 0; j < n; ++j) {
graph[i][j] = false;
}
}
int first, second;
for (int i = 0; i < m; ++i) {
fin >> first;
fin >> second;
graph[first - 1][second - 1] = true;
}
stack<int> sol;
topologicalSort(&sol, graph, visited, 0, n);
while (!sol.empty()) {
fout << sol.top() << ' ';
sol.pop();
}
for (int i = 0; i < n; ++i) {
free(graph[i]);
}
free(graph);
free(visited);
return 0;
}
bool hasUnvisitedNeighbors(bool** graph, bool* visited, int currentNode, int size) {
for (int i = 0; i < size; ++i) {
if (graph[currentNode][i] && visited[i]) {
return true;
}
}
return false;
}
void topologicalSort(stack<int>* sol, bool** graph, bool* visited, int currentNode, int size) {
visited[currentNode] = true;
for (int i = 0; i < size; ++i) {
if (i == currentNode) {
continue;
}
if (graph[currentNode][i] && !visited[i]) {
topologicalSort(sol, graph, visited, i, size);
}
}
sol->push(currentNode + 1);
}