Pagini recente » Cod sursa (job #1058673) | Cod sursa (job #835664) | Cod sursa (job #171140) | Cod sursa (job #1729261) | Cod sursa (job #1003418)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int NMAX = 100003;
vector <int> G[NMAX], R[NMAX];
stack <int> S;
int cnt, downlink[NMAX], order[NMAX], s;
void tarjan (const int &node) {
vector <int> :: iterator i;
S.push (node);
downlink[node] = ++cnt;
order[node] = cnt;
for (i = G[node].begin (); i != G[node].end (); ++i)
if (!order[*i])
tarjan (*i),
downlink[node] = min (downlink[node], downlink[*i]);
else
if (order[*i] != -1)
downlink[node] = min (downlink[node], downlink[*i]);
if (order[node] == downlink[node]) {
++s;
int cnode = S.top ();
S.pop ();
while (cnode != node)
R[s].push_back (cnode),
order[cnode] = -1,
cnode = S.top (),
S.pop ();
R[s].push_back (node);
order[node] = -1;
}
}
int main () {
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
int N, M, a, b, i;
vector <int> :: iterator j;
scanf ("%d%d", &N, &M);
for (i = 1; i <= M; ++i)
scanf ("%d%d", &a, &b),
G[a].push_back (b);
for (i = 1; i <= N; ++i)
if (!order[i])
tarjan (i);
printf ("%d", s);
for (i = 1; i <= s; ++i) {
printf ("\n");
for (j = R[i].begin (); j != R[i].end (); ++j)
printf ("%d ", *j);
}
}