Pagini recente » Istoria paginii runda/bac-calinush | Cod sursa (job #1675372) | Cod sursa (job #1518938) | Istoria paginii utilizator/kamikaze | Cod sursa (job #1330766)
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <list> // Varianta 1 = V1 / Introduction to Alg: DFS, lista by finish time
#include <vector> // Varianta 2 = V2 / Infoarena: Queue by 0-inDegree
#include <typeinfo>
using namespace std;
#define DMAX 50003
int N, M, timeR; // timeR is for V1
list<int> L; // V1
vector<int> Q; // V2 - "coada"
struct Nod{
int d, f, u, inDegree;
vector<int> Adj; // outList
}G[DMAX];
void citire(){
int i, j, x, y;
cin >> N >> M;
for (i = 0; i < M; i++){
cin >> x >> y;
G[x].Adj.push_back(y);
G[y].inDegree++;
}
}
void DFS(int root){
int i, lg = G[root].Adj.size(), chld;
G[root].d = ++timeR;
G[root].u = 1;
for (i = 0; i < lg; i++){
chld = G[root].Adj[i];
if (!G[chld].u){
DFS(chld);
}
}
G[root].f = ++timeR;
L.push_front(root);
}
void solve_V1(){
for (int i = 1; i <= N; i++){
if (!G[i].inDegree){
DFS(i);
}
}
}
void solve_V2(){
int i, j, lg, chld;
for (i = 1; i <= N; i++){
if (!G[i].inDegree)
Q.push_back(i);
}
for (i = 0; i < Q.size(); i++){ // Q.size() creste pana am parcurs toate vf
lg = G[Q[i]].Adj.size();
for (j = 0; j < lg; j++){
chld = G[Q[i]].Adj[j];
if (--G[chld].inDegree == 0){
Q.push_back(chld);
}
}
}
}
int main(){
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
citire();
if (N % 2){ // alegere "random"
solve_V1(); // DFS, lista
for (auto i : L) cout << i << ' ';
}
else{
solve_V2(); // inDegree =0, Queue
for (auto i : Q) cout << i << ' ';
}
return 0;
}