Pagini recente » Cod sursa (job #1250240) | Cod sursa (job #342377) | Cod sursa (job #1062218) | Cod sursa (job #931293) | Cod sursa (job #1495724)
#include<stdio.h>
using namespace std;
const int N = 100001, M = 2*200002;
int vf[M], urm[M], lst[N], nr = 0, v[N], c, rez[M], c2, x2[M], y2[M];
bool viz[N];
void adauga(int x, int y)
{
nr++;
vf[nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void dfs1 (int x)
{
int p, y;
p = lst[x];
viz[x] = true;
while (p != 0)
{
y = vf[p];
if (viz[y] == false)
{
dfs1(y);
v[++c] = y;
}
p = urm[p];
}
}
void dfs2 (int x)
{
int p, y;
p = lst[x];
viz[x] = true;
rez[++c2] = x;
while (p != 0)
{
y = vf[p];
if (viz[y] == false)
dfs2(y);
p = urm[p];
}
}
int main ()
{
FILE *in, *out;
in = fopen ("ctc.in", "r");
out = fopen ("ctc.out", "w");
int n, m;
fscanf (in, "%d%d", &n, &m);
int i, x, y;
for (i = 1; i <= m; i++)
{
fscanf (in, "%d%d", &x, &y);
x2[i] = x;
y2[i] = y;
adauga (x, y);
}
for (i = 1; i <= n; i++)
if (viz[i] == 0)
{
dfs1(i);
v[++c] = i;
}
for (i = 1; i <= n; i++)
{
lst[i] = 0;
viz[i] = false;
}
for (i = 1; i <= m; i++)
{
vf[i] = 0;
urm[i] = 0;
}
for (i = 1; i <= m; i++)
adauga(y2[i], x2[i]);
int comp = 0;
for (i = n; i >= 1; i--)
if (viz[v[i]] == 0)
{
comp++;
dfs2(v[i]);
rez[++c2] = -1;
}
fprintf (out, "%d\n", comp);
c = 1;
for (i = 1; i <= comp; i++)
{
while (rez[c] != -1)
{
fprintf (out, "%d ", rez[c]);
c++;
}
c++;
fprintf (out, "\n");
}
return 0;
}