Pagini recente » Cod sursa (job #2694162) | Cod sursa (job #1376930) | Cod sursa (job #1258817) | Cod sursa (job #1329426) | Cod sursa (job #2919294)
#include <iostream>
#include<fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class Graph{
private:
int n_nodes;
vector<vector<int>> adj;
vector<pair< int , pair<int,int>> > adj_weight;
public:
Graph(){
n_nodes = 0;
adj = {};
}
Graph(int n, vector<vector<int>> &gr){
n_nodes = n;
adj = gr;
}
void dfs_ctc(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution);
void solve_sort_top();
};
void Graph:: dfs_ctc(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution){
visited[node] = true;
for(auto &x: gr[node]){
if(!visited[x]) dfs_ctc(x, visited, gr, solution);
}
solution.push_back(node);
}
void Graph::solve_sort_top(){
vector<bool> v(n_nodes+1, false);
vector<int> sol(n_nodes+1);
for(int i = 1; i <= n_nodes; ++i){
if(!v[i]) dfs_ctc(i, v, adj, sol);
}
reverse(sol.begin(), sol.end());
for(int i = 0; i < n_nodes; ++i)
//cout<<sol[i]<<' ';
fout<<sol[i]<<' ';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, x, y;
// cin>>n>>m;
fin>>n>>m;
vector<vector<int>> aux(n+1);
for(int i = 0; i < m; ++i){
// cin>>x>>y;
fin>>x>>y;
aux[x].push_back(y);
}
Graph g = Graph(n, aux);
g.solve_sort_top();
return 0;
}