Pagini recente » Cod sursa (job #1568766) | Cod sursa (job #1605042) | Cod sursa (job #2814993) | Cod sursa (job #1876182) | Cod sursa (job #3198020)
///topological sort based on dfs
///perform a dfs, store the fiinishing time for every vertex
///solution = the vertices in the reverse order of finishing time
#include <bits/stdc++.h>
using namespace std;
int N, M, nr;
vector<int>L[50002];///adjacency list
int vis[50002], topoSort[50002];
ifstream in("sortaret.in");
ofstream out("sortaret.out");
void dfs(int k){
vis[k] = 1; ///grey
for(int i = 0; i < L[k].size(); i++){
int j = L[k][i];
if(vis[j] == 0) dfs(j);
}
vis[k] = 2;///black
topoSort[nr] = k;///reverse order
nr = nr - 1;
}
int main(){
in >> N >> M;
nr = N;
for(int i = 1; i <= N; i++){
int x, y;
in >> x >> y;
L[x].push_back(y);
}
for(int i = 1; i <= N; i++)
if(vis[i] == 0) dfs(i); ///if i is white perform a dfs starting with i
for(int i = 1; i <= N; i++) out << topoSort[i] << " ";
return 0;
}