Pagini recente » Cod sursa (job #1155704) | Cod sursa (job #395081) | Cod sursa (job #792810) | Cod sursa (job #2585125) | Cod sursa (job #2792678)
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
std::ifstream f("sortaret.in");
std::ofstream fg("sortaret.out");
int n, m, a, b;
class graf{
public:
int n, m;
graf(int n, int m);
std::map<int, std::vector<int> > lista;
std::vector<int> viz;
std::deque<int> coada;
void new_lista( int nod1, int nod2);
void dfs(int nod);
void sortare();
};
graf::graf(int n, int m) {
this->n = n;
this->m = m;
}
void graf::new_lista(int nod1, int nod2){
lista[nod1].push_back(nod2);
//lista[nod2].push_back(nod1);
}
void graf::dfs(int nod){
static int cnt = 0;
viz[nod] = ++cnt;
for( auto i = lista[nod].begin(); i != lista[nod].end(); i++) {
if (viz[*i] == -1) dfs(*i);
}
coada.push_back(nod);
}
void graf::sortare(){
for(auto i = 0 ; i<=n ; i++){
viz.push_back(-1);
}
for(int i = 0 ; i< n ; i++){
if(viz[i] == -1) dfs(i);
}
/*for(int i=0 ; i<n ; i++)
std::cout<<viz[i]<<" ";*/
while(!coada.empty()){
int aux = coada.back();
fg<<aux + 1<<" ";
coada.pop_back();
}
}
int main() {
f>>n>>m;
graf g(n, m);
for(int i=0 ; i<m ; i++){
f>>a>>b;
g.new_lista(a-1,b-1);
}
g.sortare();
return 0;
}