Pagini recente » Cod sursa (job #2131563) | Cod sursa (job #2710929) | Cod sursa (job #2552011) | Cod sursa (job #1802162) | Cod sursa (job #1095954)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100003
int n, m, count, ksol, index[NMAX], lp[NMAX];
vector <int> v[NMAX], sol[NMAX];
stack <int> s;
bool used[NMAX];
void ReadData ()
{
scanf ("%d %d", &n, &m);
for (int i = 1, a, b; i <= m; ++i)
{
scanf ("%d %d", &a, &b);
v[a].push_back (b);
}
}
void Tarjan (int k)
{
++count;
index[k] = count;
lp[k] = count;
s.push (k);
used[k] = true;
for (int i = 0; i < v[k].size (); ++i)
{
if (index[v[k][i]] == 0)
{
Tarjan (v[k][i]);
if (lp[v[k][i]] < lp[k])
lp[k] = lp[v[k][i]];
}
else if (used[v[k][i]] && lp[v[k][i]] < lp[k])
lp[k] = lp[v[k][i]];
}
if (index[k] == lp[k])
{
++ksol;
while (s.top () != k)
{
used[s.top ()] = false;
sol[ksol].push_back (s.top ());
s.pop ();
}
used[s.top ()] = false;
sol[ksol].push_back (s.top ());
s.pop ();
}
}
int main ()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
ReadData ();
for (int i = 1; i <= n; ++i)
{
if (index[i] == 0)
Tarjan (i);
}
printf ("%d\n", ksol);
for (int i = 1; i <= ksol; ++i)
{
for (int j = 0; j < sol[i].size (); ++j)
printf ("%d ", sol[i][j]);
printf ("\n");
}
return 0;
}