Pagini recente » Cod sursa (job #965396) | Cod sursa (job #1961480) | Cod sursa (job #65865) | Cod sursa (job #1293170) | Cod sursa (job #2118081)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int> v[1000], lista;
int s, n, m, color[1000], time[1000], t;
void citire () {
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
v[x].push_back(y);
}
}
/// if there is any edge other than "tree", then the graph has at least a cycle
void dfs (int nod) {
color[nod] = 1;
t += 1;
time[nod] = t;
int size = v[nod].size();
for (int i = 0; i < size; ++i) {
int y = v[nod][i];
if (color[y] == 0) {
//cout << nod << " " << y << " " << "tree" << '\n';
dfs(y);
}
else {
if (color[y] == 1) {
// cout << nod << " " << y << " " << "back" << '\n';
}
if (color[y] == 2) {
if (time[nod] < time[y]) {
//cout << nod << " " << y << " " << "forward" << '\n';
}
else {
// cout << nod << " " << y << " " << "cross" << '\n';
}
}
}
}
color[nod] = 2;
t += 1;
lista.push_back(nod);
}
int main () {
citire();
dfs(1);
int size = lista.size();
for (int i = size-1; i >= 0; i--) {
fout << lista[i] << " ";
}
}