Pagini recente » Cod sursa (job #914599) | Cod sursa (job #3145028) | Cod sursa (job #1061782) | Cod sursa (job #2624627) | Cod sursa (job #2122437)
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 50005;
int n, m;
int globalIndex;
int index[NMAX], lowlink[NMAX];
vector<int> g[NMAX];
vector<int> topsort;
stack<int> st;
bitset<NMAX> v;
void read() {
ifstream in("sortaret.in");
in >> n >> m;
int x, y;
for (int i = 1; i <= m; i++) {
in >> x >> y;
g[x].push_back(y);
}
}
void dfs(int x) {
v[x] = 1;
st.push(x);
index[x] = lowlink[x] = ++globalIndex;
for (int y : g[x]) {
if (!index[y]) {
dfs(y);
lowlink[x] = min(lowlink[x], lowlink[y]);
} else if (v[y]) {
lowlink[x] = min(lowlink[x], index[y]);
}
}
if (lowlink[x] == index[x]) {
int y;
do {
y = st.top();
st.pop();
topsort.push_back(y);
} while (y != x);
}
}
int main() {
read();
for (int i = 1; i <= n; i++)
if (!index[i])
dfs(i);
ofstream out("sortaret.out");
for (int x : topsort)
out << x << " ";
return 0;
}