Pagini recente » Cod sursa (job #2826752) | Cod sursa (job #1769385) | Cod sursa (job #2433925) | Cod sursa (job #1910531) | Cod sursa (job #2979196)
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a[2][200005], start[100005], a1[2][200005], start1[200005], nr, p[100005], mi[100005], viz[100005], sol[100005], 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) {
viz[i] = 1;
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;
}
}