Pagini recente » Cod sursa (job #2241686) | Cod sursa (job #1270326) | Cod sursa (job #747681) | Cod sursa (job #2815523) | Cod sursa (job #2238060)
#include <cstdio>
#include <cstdlib>
using namespace std;
int n, m, *a[100005], *atr[100005], checked[100005], postorder[100005], peak, *ctc[100005], nr_ctc;
void dfs(int x)
{
checked[x] = 1;
for (int i = 1; i <= a[x][0]; ++i)
if (!checked[a[x][i]])
dfs(a[x][i]);
postorder[++peak] = x;
}
void dfs_tr(int x)
{
checked[x] = 0;
++ctc[nr_ctc][0];
ctc[nr_ctc] = (int *)realloc(ctc[nr_ctc], (ctc[nr_ctc][0] + 1) * sizeof(int));
ctc[nr_ctc][ctc[nr_ctc][0]] = x;
for (int i = 1; i <= atr[x][0]; ++i)
if (checked[atr[x][i]])
dfs_tr(atr[x][i]);
}
int main()
{
FILE *in, *out;
in = freopen("ctc.in", "r", stdin);
out = freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
a[i] = (int *)realloc(a[i], sizeof(int));
a[i][0] = 0;
atr[i] = (int *)realloc(atr[i], sizeof(int));
atr[i][0] = 0;
ctc[i] = (int *)realloc(ctc[i], sizeof(int));
ctc[i][0] = 0;
}
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
++a[x][0];
a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
a[x][a[x][0]] = y;
++atr[y][0];
atr[y] = (int *)realloc(atr[y], (atr[y][0] + 1) * sizeof(int));
atr[y][atr[y][0]] = x;
}
fclose(in);
for (int i = 1; i <= n; ++i)
if (!checked[i])
dfs(i);
for (int i = n; i; --i)
if (checked[postorder[i]]) {
++nr_ctc;
dfs_tr(postorder[i]);
}
printf("%d\n", nr_ctc);
for (int i = 1; i <= nr_ctc; ++i) {
for (int j = 1; j <= ctc[i][0]; ++j)
printf("%d ", ctc[i][j]);
printf("\n");
}
fclose(out);
return 0;
}