Pagini recente » Cod sursa (job #1235606) | Profil Zamolxis25 | Cod sursa (job #122250) | Cod sursa (job #437208) | Cod sursa (job #526947)
Cod sursa(job #526947)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int N;
vector<vector<int> > adj;
vector<vector<int> > rev;
vector<vector<int> > sol;
vector<bool> viz;
stack<int> finished;
void dfs1(int nod) {
if (viz[nod]) return;
viz[nod] = true;
for (int i = 0; i < adj[nod].size(); ++i) {
dfs1(adj[nod][i]);
}
finished.push(nod);
}
void dfs2(int nod, vector<int> &csol) {
if (!viz[nod]) return;
csol.push_back(nod);
viz[nod] = false;
for (int i = 0; i < rev[nod].size(); ++i) {
dfs2(rev[nod][i], csol);
}
}
int main(void) {
int M;
freopen ("ctc.in", "rt", stdin);
freopen ("ctc.out", "wt", stdout);
scanf("%d %d", &N, &M);
adj.resize(N + 1);
rev.resize(N + 1);
viz.resize(N + 1);
while (M--) {
int x, y;
scanf ("%d %d", &x, &y);
adj[x].push_back(y);
rev[y].push_back(x);
}
for (int i = 1; i <= N; ++i) dfs1(i);
while (!finished.empty()) {
if (viz[finished.top()]) {
vector<int> csol;
dfs2(finished.top(), csol);
sol.push_back(csol);
}
finished.pop();
}
printf ("%d\n", (int)sol.size());
for (int i = 0; i < sol.size(); ++i) {
for (int j = 0; j < sol[i].size(); ++j) {
printf ("%s%d", j ? " " : "", sol[i][j]);
}
printf("\n");
}
return 0;
}