Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Diferente pentru preoni-2007/runda-4/solutii intre reviziile 34 si 20 | Istoria paginii runda/testround4/clasament | Cod sursa (job #1707069)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
vector <int> v[100010], iv[100010];
stack <int> st, cst;
bool ap[100010];
inline void dfs (int nod)
{
ap[nod] = true;
for (auto &it : v[nod])
if (!ap[it]) dfs (it);
st.push (nod);
cst.push (nod);
}
inline void df (int nod, bool OK)
{
if (OK) printf ("%d ", nod);
ap[nod] = true;
for (auto &it : iv[nod])
if (!ap[it]) df (it, OK);
}
int main ()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
int n, m;
scanf ("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
{
int x, y;
scanf ("%d %d", &x, &y);
v[x].push_back (y);
iv[y].push_back (x);
}
for (int i = 1; i <= n; ++i)
if (!ap[i]) dfs (i);
memset (ap, false, sizeof (ap));
int nr = 0;
while (!st.empty ())
{
int x = st.top ();
st.pop ();
if (!ap[x]) df (x, false), ++nr;
}
st.swap (cst);
memset (ap, false, sizeof (ap));
printf ("%d\n", nr);
while (!st.empty ())
{
int x = st.top ();
st.pop ();
if (!ap[x])
{
df (x, true);
printf ("\n");
}
}
return 0;
}