Pagini recente » Cod sursa (job #323066) | Cod sursa (job #2149606) | Cod sursa (job #1176647) | Cod sursa (job #943536) | Cod sursa (job #2979232)
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a[2][20005], start[10005], a1[2][20005], start1[10005], nr, p[10005], mi[10005], viz[10005], sol[10005], lg;
void df1(int nod);
void df2(int nod);
void plusminus();
int main()
{
int i, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++) {
fin >> x >> y;
a[0][i] = y;
a[1][i] = start[x];
start[x] = i;
a1[0][i] = x;
a1[1][i] = start1[y];
start1[y] = i;
}
plusminus();
fout << nr << "\n";
for (i = 1; i <= lg; i++)
if (sol[i] > 0)
fout << sol[i] << " ";
else
fout << "\n";
return 0;
}
void df1(int nod)
{
int x;
p[nod] = 1;
x = start[nod];
while (x) {
if (p[a[0][x]] == 0)
df1(a[0][x]);
x = a[1][x];
}
}
void df2(int nod)
{
int x;
mi[nod] = 1;
x = start1[nod];
while (x) {
if (mi[a1[0][x]] == 0)
df2(a1[0][x]);
x = a1[1][x];
}
}
void plusminus()
{
int i, j;
for (i = 1; i <= n; i++)
if (viz[i] == 0) {
nr++;
for (j = 1; j <= n; j++)
p[j] = mi[j] = 0;
df1(i);
df2(i);
for (j = 1; j <= n; j++)
if (p[j] && mi[j]) {
sol[++lg] = j;
viz[j] = 1;
}
sol[++lg] = -1;
}
}