Pagini recente » Cod sursa (job #811765) | Cod sursa (job #2988374) | Cod sursa (job #1853337) | Cod sursa (job #2935796) | Cod sursa (job #2713424)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream be("sortaret.in");
ofstream ki("sortaret.out");
void beolvas(vector<vector<int>> &graf,int n, int m);
void topo_rendezes(const vector<vector<int>> &graf, int n);
void DFS(const vector<vector<int>> &graf, vector<bool> &latogatott,vector<int> &topo_sorrend,int kezdo);
int main(){
int n, m;
be >> n >> m;
vector<vector<int>> graf(n);
beolvas(graf, n, m);
topo_rendezes(graf, n);
}
void beolvas(vector<vector<int>>& graf, int n, int m) {
for (int i = 0; i < m; i++) {
int x, y;
be >> x >> y;
graf[x - 1].push_back(y - 1);
}
}
void topo_rendezes(const vector<vector<int>> &graf, int n) {
vector<bool> latogatott(n, false);
vector<int> topo_sorrend;
for (int i = 0; i < n; i++)
if (!latogatott[i]) DFS(graf, latogatott, topo_sorrend, i);
for (int i = topo_sorrend.size() - 1; i >= 0; i--)
ki << topo_sorrend[i] + 1 << " ";
}
void DFS(const vector<vector<int>> &graf, vector<bool>& latogatott, vector<int>& topo_sorrend, int kezdo) {
latogatott[kezdo] = true;
for (int i : graf[kezdo])
if (!latogatott[i]) DFS(graf, latogatott, topo_sorrend, i);
topo_sorrend.push_back(kezdo);
}