Pagini recente » Cod sursa (job #1813550) | Cod sursa (job #2403818) | Cod sursa (job #1536728) | Cod sursa (job #3234553) | Cod sursa (job #1963425)
/*
skel_graph - DFS
*/
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <bitset>
#include <cassert>
#include <stack>
#define NMAX 100009 // ATENTIE la cat e in problema curenta !!!
#define MMAX 500009 // ATENTIE la cat e in problema curenta !!!
using namespace std;
int n, m;
int p[NMAX];
vector<int> G[NMAX];
vector<int> Gtr[NMAX];
bitset<NMAX> used;
void read_input() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
}
}
void dfs(int node, stack<int>& st) {
used[node] = 1;
for (auto it = G[node].begin(); it != G[node].end(); ++it) {
if (!used[ *it ]) {
dfs(*it, st);
}
}
st.push(node);
}
void dfsT(int node) {
used[node] = 1;
cout << node << " ";
for (auto it = Gtr[node].begin(); it != Gtr[node].end(); ++it) {
if (!used[ *it ]) {
dfsT(*it);
}
}
}
void ctc() {
stack<int> st;
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs(i, st);
}
}
// Get graph transpose
for (int i = 1; i <= n; i++) {
for (auto it = G[i].begin(); it != G[i].end(); ++it) {
Gtr[*it].push_back(i);
}
}
for (int i = 0; i <=n; i++) {
used[i] = 0;
}
while (!st.empty()) {
int v = st.top();
st.pop();
if (!used[v]) {
dfsT(v);
cout << "\n";
}
}
}
void print_output() {
}
// puteti pastra main-ul mereu cum e acum
int main() {
// las linia urmatoare daca citesc din fisier
assert( freopen("in", "r", stdin) != NULL);
// las linia urmatoare daca afisez in fisier
// assert( freopen("out", "w", stdout) != NULL) ;
read_input();
ctc();
print_output();
return 0;
}