Pagini recente » Cod sursa (job #1241483) | Cod sursa (job #1281371) | Cod sursa (job #3155370) | Cod sursa (job #2796927) | Cod sursa (job #2980375)
#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[100005], viz[100005], st[100005], vf, sol[200005], lg, nrc;
void dfp(int nod);
void dfm(int nod);
void kosajaru();
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;
}
kosajaru();
return 0;
}
void dfp(int nod)
{
int x;
viz[nod] = 1;
x = start[nod];
while (x) {
if (viz[a[0][x]] == 0)
dfp(a[0][x]);
x = a[1][x];
}
st[++vf] = nod;
}
void dfm(int nod)
{
int x;
viz[nod] = 2;
sol[++lg] = nod;
x = start1[nod];
while (x) {
if (viz[a1[0][x]] == 1)
dfm(a1[0][x]);
x = a1[1][x];
}
}
void kosajaru()
{
int i, nod;
for (i = 1; i <= n; i++)
if (viz[i] == 0)
dfp(i);
while (vf) {
nod = st[vf];
if (viz[nod] == 1) {
nrc++;
dfm(nod);
sol[++lg] = -1;
}
vf--;
}
fout << nrc << "\n";
for (i = 1; i <= lg; i++) {
if (sol[i] == -1)
fout << "\n";
else
fout << sol[i] << " ";
}
}