Pagini recente » Cod sursa (job #2001375) | Cod sursa (job #1239665) | Cod sursa (job #2866500) | Cod sursa (job #1709800) | Cod sursa (job #1182190)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
#define DMAX 50001
struct Graph{
char inf[DMAX]; // content
char color[DMAX]; // w->g->b
int parent[DMAX], d[DMAX], f[DMAX]; // d = discovered, f = finished
vector<int> Adj[DMAX]; // Adj list
vector<pair<int, int>> Edge;
} G;
int N, M, timp;
list<int> L;
list<int>::iterator l;
void DFS_VISIT(int root){
int i, lg, next;
timp++;
G.color[root] = 'g';
G.d[root] = timp;
lg = G.Adj[root].size();
for (i = 0; i < lg; i++){
next = G.Adj[root][i];
if (G.color[next] == 'w')
DFS_VISIT(next);
}
timp++;
G.color[root] = 'b';
G.f[root] = timp;
L.push_front(root);
}
void DFS(){
int i;
for (i = 1; i <= N; i++){
G.color[i] = 'w';
G.parent[i] = 0;
}
for (i = 1; i <= N; i++){
if (G.color[i] == 'w'){
DFS_VISIT(i);
}
}
}
int main(){
int i, ui, vi;
fin >> N >> M;
for (i = 0; i < M; i++) {
fin >> ui >> vi;
G.Adj[ui].push_back(vi);
G.Edge.push_back(make_pair(ui, vi));
}
DFS();
for (l = L.begin(); l != L.end(); l++) fout << *l << ' ';
return 0;
}