Pagini recente » Cod sursa (job #1981073) | Cod sursa (job #674169) | Cod sursa (job #1943478) | Cod sursa (job #2857737) | Cod sursa (job #2907881)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector <vector <int> > graph;
vector <int> dfsOrder;
vector <bool> visited;
void dfs(int startNode){
visited[startNode] = true;
for(unsigned int i = 0; i < graph[startNode].size(); ++i){
int vecin = graph[startNode][i];
if(!visited[vecin]){
//visited[vecin] = true;
dfs(vecin);
}
}
dfsOrder.push_back(startNode);
}
void topSort(){
for(unsigned int i = 1; i < graph.size(); ++i){
if(!visited[i]){
dfs(i);
}
}
reverse(dfsOrder.begin(), dfsOrder.end());
}
int main()
{
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
f >> n >> m;
cout << "yes";
visited.assign(n + 1, false);
graph.resize(n + 1);
while(m) {
int x, y;
f >> x >> y;
cout << "yes";
graph[x].push_back(y);
m--;
}
topSort();
for(unsigned int i = 0; i < dfsOrder.size(); ++i) {
g << dfsOrder[i] << " ";
}
return 0;
}