Pagini recente » Cod sursa (job #3288976) | Mall | Profil Ionut228 | Cod sursa (job #2712056) | Cod sursa (job #1184540)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
const int dim = 100005;
int N, M, NCTC, dfn[dim], low[dim], index;
vector <int> CTC[dim], V[dim];
stack <int> S;
void ctc (int n, int t)
{
S.push(n);
dfn[n] = low[n] = ++index;
for (int i = 0, f; i < V[n].size(); i++)
{
f = V[n][i];
if (dfn[f] == 0)
{
ctc (f, n);
low[n] = min (low[n], low[f]);
}
else
{
low[n] = min (low[n], dfn[f]);
}
}
if (low[n] == dfn[n])
{
NCTC++;
int last;
do
{
last = S.top();
S.pop ();
CTC[NCTC].push_back (last);
} while (last != n);
}
}
int main()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
scanf ("%d%d", &N, &M);
for (int i = 1, a, b; i <= M; i++)
{
scanf ("%d%d", &a, &b);
V[a].push_back (b);
}
for (int n = 1; n <= N; n++)
{
if (dfn[n] == 0)
{
ctc (n, 0);
}
}
printf ("%d\n", NCTC);
for (int c = 1, i, n; c <= NCTC; c++)
{
for (i = 0; i < CTC[c].size(); i++)
{
n = CTC[c][i];
printf ("%d ", n);
}
printf ("\n");
}
return 0;
}