Pagini recente » Istoria paginii autumn-warmup-2007/clasament/runda-2 | Istoria paginii runda/proba_de_pregatire_ioit/clasament | Cod sursa (job #1796796) | Autentificare | Cod sursa (job #1707070)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int NMAX = 100000 + 5;
vector <int> g[NMAX],gt[NMAX];
int n,m,N,ret,st[NMAX],x,y;
bool sel[NMAX];
inline void df1(int x)
{
sel[x] = true;
for (int i = 0 ; i<g[x].size(); ++i)
if (sel[g[x][i]]==false)
{
df1(g[x][i]);
}
st[++N] = x;
}
inline void df2(int x, bool ok)
{
sel[x] = true;
if (ok==true)printf("%d ", x);
for (int i = 0; i<gt[x].size(); ++i)
if (sel[gt[x][i]]==false)
df2(gt[x][i], ok);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d", &n,&m);
for (int i = 1; i<=m; ++i)
{
scanf("%d %d", &x,&y);
g[x].pb(y);
gt[y].pb(x);
}
for (int i = 1; i<=n; ++i)
if (!sel[i])
df1(i);
memset(sel,false,sizeof(sel));
for (int i = N ; i>=1; --i)
if (!sel[st[i]])
{
++ret;
df2(st[i], false);
}
memset(sel,false,sizeof(sel));
printf("%d\n", ret);
for (int i = N; i>=1; --i)
if (!sel[st[i]])
{
df2(st[i],true);
printf("\n");
}
return 0;
}