Pagini recente » Cod sursa (job #2032277) | Cod sursa (job #2152345) | Cod sursa (job #277995) | Cod sursa (job #887962) | Cod sursa (job #526661)
Cod sursa(job #526661)
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define DIM 100005
vector <int> g[DIM],gt[DIM],ct[DIM];
int postviz[DIM];
int n,m,nrc,ctc;
bool viz[DIM];
void read ()
{
int i,x,y;
scanf ("%d%d",&n,&m);
for (i=1; i<=m; ++i)
{
scanf ("%d%d",&x,&y);
g[x].pb (y);
gt[y].pb (x);
}
}
void df (int nod)
{
vector <int> :: iterator it;
viz[nod]=1;
for (it=g[nod].begin (); it!=g[nod].end (); ++it)
if (!viz[*it])
df (*it);
postviz[++nrc]=nod;
}
void dft (int nod)
{
vector <int> :: iterator it;
viz[nod]=0;
ct[ctc].pb (nod);
for (it=gt[nod].begin (); it!=gt[nod].end (); ++it)
if (viz[*it])
dft (*it);
}
void solve ()
{
int i;
for (i=1; i<=n; ++i)
if (!viz[i])
df (i);
for (i=n; i>=1; --i)
if (viz[postviz[i]])
{
++ctc;
dft (postviz[i]);
}
}
void print ()
{
vector <int> :: iterator it;
int i;
printf ("%d\n",ctc);
for (i=1; i<=ctc; ++i)
{
for (it=ct[i].begin (); it!=ct[i].end (); ++it)
printf ("%d ",*it);
printf ("\n");
}
}
int main ()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
read ();
solve ();
print ();
return 0;
}