Pagini recente » Cod sursa (job #1375919) | Cod sursa (job #1183137) | Cod sursa (job #619030) | Cod sursa (job #2052105) | Cod sursa (job #1918107)
#include<stdio.h>
using namespace std;
const int N = 100005, M = 200005;
int vf[M], urm[M], lst[N], nr, noduri[N], sol[2 * N], x[M], y[M];
bool viz[N];
void adauga (int x, int y)
{
vf[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void dfs (int x2)
{
viz[x2] = true;
int p, y2;
p = lst[x2];
while (p != 0)
{
y2 = vf[p];
if (viz[y2] == false)
dfs (y2);
p = urm[p];
}
noduri[++nr] = x2;
}
void curata (int n, int m)
{
int i;
for (i = 1; i <= m; i++)
vf[i] = urm[i] = 0;
for (i = 1; i <= n; i++)
lst[i] = viz[i] = 0;
}
void dfs2 (int x2)
{
viz[x2] = true;
sol[++nr] = x2;
int p, y2;
p = lst[x2];
while (p != 0)
{
y2 = vf[p];
if (viz[y2] == false)
dfs2 (y2);
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;
for (i = 1; i <= m; i++)
{
fscanf (in, "%d%d", &x[i], &y[i]);
adauga (x[i], y[i]);
}
nr = 0;
for (i = 1; i <= n; i++)
if (viz[i] == false)
dfs (i);
nr = 0;
curata (n, m);
for (i = 1; i <= m; i++)
adauga (y[i], x[i]);
nr = 0;
int nrSol = 0;
for (i = n; i >= 1; i--)
if (viz[noduri[i]] == false)
{
dfs2(noduri[i]);
sol[++nr] = -1;
nrSol++;
}
fprintf (out, "%d\n", nrSol);
for (i = 1; i <= nr; i++)
{
if (sol[i] != -1)
fprintf (out, "%d ", sol[i]);
else
fprintf (out, "\n");
}
return 0;
}