Pagini recente » Cod sursa (job #878300) | Cod sursa (job #528216) | Cod sursa (job #870992) | Cod sursa (job #959421) | Cod sursa (job #1262551)
#include<stdio.h>
using namespace std;
const int L = 200000, N = 100000;
int urm[L], rez[L], v[L], vf[L], lst[N], urm2[L], vf2[L], lst2[N], nr = 0, nr2=0, ct1 = 0, ct2 = 0;
bool viz[L*2];
FILE *in, *out;
void adauga1(int x, int y)
{
vf[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void adauga2(int x, int y)
{
vf2[++nr2] = y;
urm2[nr2] = lst2[x];
lst2[x] = nr2;
}
void dfs (int x)
{
int p, y;
viz[x] = true;
p = lst[x];
while (p != 0)
{
y = vf[p];
if (!viz[y])
dfs(y);
p = urm[p];
}
v[++ct1] = x;
}
void dfs2 (int x)
{
int p, y;
viz[x] = true;
p = lst2[x];
rez[++ct2] = x;
while (p != 0)
{
y = vf2[p];
if (!viz[y])
{
dfs2(y);
}
p = urm2[p];
}
}
int main ()
{
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);
adauga1(x,y);
adauga2(y,x);
}
int ct = 0;
for (i = 1; i <= n; i++)
if (viz[i] == 0)
dfs(i);
for (i = 1; i <= n; i++)
viz[i] = 0;
for (i = n; i >= 1; i--)
if (viz[v[i]] == 0){
dfs2(v[i]);
rez[++ct2] = -1;
ct++;
}
i = 1;
fprintf(out, "%d\n", ct);
while (rez[i] != 0)
{
if (rez[i] == -1)
fprintf(out, "\n");
else
fprintf(out, "%d ", rez[i]);
i++;
}
return 0;
}