Pagini recente » Cod sursa (job #3262977) | Cod sursa (job #2916534) | Cod sursa (job #3234202) | Flux si cuplaj | Cod sursa (job #485667)
Cod sursa(job #485667)
#include <cstdio>
#include <vector>
using namespace std;
#define pb push_back
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
const int MAX_N = 100001;
int n, m, nr_sol, z;
int a[MAX_N];
char f[MAX_N];
vector <int> v[MAX_N], vt[MAX_N], sol[MAX_N];
void df(int nod)
{
if (f[nod])
return;
f[nod] = 1;
forit(it, v[nod])
df(*it);
a[++z] = nod;
}
void df2(int nod)
{
if (f[nod] == 2)
return;
f[nod] = 2;
sol[nr_sol].pb(nod);
forit(it, vt[nod])
df2(*it);
}
int main()
{
int i;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
v[x].pb(y);
vt[y].pb(x);
}
for (i = 1; i <= n; ++i)
if (!f[i])
df(i);
for (i = n; i; --i)
if (f[a[i]] != 2)
{
++nr_sol;
df2(a[i]);
}
printf("%d\n", nr_sol);
for (i = 1; i <= nr_sol; ++i)
{
forit(it, sol[i])
printf("%d ", *it);
printf("\n");
}
}