Pagini recente » Cod sursa (job #3278574) | Cod sursa (job #2662494) | Cod sursa (job #1980121) | Cod sursa (job #627378) | Cod sursa (job #3264126)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<int> rez;
void dfs(vector <int> g[], int node, int viz[]) {
//cout << node << " ";
viz[node] = 1;
for (auto next : g[node])
if (!viz[next])
dfs(g, next, viz);
return;
}
void dfsDemo() {
vector <int> g[5];
//1 - 2
g[1].push_back(2);
g[2].push_back(1);
//1 - 3
g[1].push_back(3);
g[3].push_back(1);
//2 - 4
g[2].push_back(4);
g[4].push_back(2);
//2 - 3
g[2].push_back(3);
g[3].push_back(2);
for (int i = 1; i <= 4; ++i) {
cout << i << ": ";
for (auto node : g[i])
cout << node << " ";
cout << "\n";
}
int viz[5] = {0};
dfs(g, 1, viz);
return;
}
void topSort(vector <int> g[], int node, int viz[]) {
rez.push_back(node);
viz[node] = 1;
for (auto next : g[node])
if (!viz[next])
topSort(g, next, viz);
return;
}
void sortareTopologica() {
vector <int> g[10];
g[1].push_back(2);
g[1].push_back(3);
g[3].push_back(4);
g[3].push_back(5);
g[5].push_back(9);
g[4].push_back(6);
g[4].push_back(7);
g[4].push_back(8);
int viz[10] = {0};
for (int i = 1; i <= 9; ++i)
if (!viz[i])
topSort(g, i, viz);
for (auto node : rez)
cout << node << " ";
return;
}
int main() {
//dfsDemo();
//sortareTopologica();
int n, m;
fin >> n >> m;
int viz[50005] = {0};
vector <int> g[n + 1];
while (m--) {
int a, b;
fin >> a >> b;
g[a].push_back(b);
}
for (int i = 1; i <= n; ++i)
if (!viz[i])
topSort(g, i, viz);
for (auto node : rez)
fout << node << " ";
return 0;
}