Pagini recente » Cod sursa (job #1018435) | Cod sursa (job #749204) | Cod sursa (job #1120557) | Cod sursa (job #1789771) | Cod sursa (job #1790390)
#include <cstdio>
#include <vector>
#define NMAX 100023
#define pb push_back
using namespace std;
int n,m;
vector<int>adj[NMAX],adjt[NMAX],sol[NMAX],stk;
int solcur;
bool vis[NMAX];
inline void citire()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
adj[a].pb(b);
adjt[b].pb(a);
}
}
void dfs1(int nod)
{
vis[nod]=1;
for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();++it)
{
if(!vis[*it]) dfs1(*it);
}
stk.pb(nod);
}
inline void topological()
{
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
}
void dfs2(int nod)
{
vis[nod]=1;
sol[solcur].pb(nod);
for(vector<int>::iterator it=adjt[nod].begin();it!=adjt[nod].end();++it)
{
if(!vis[*it]) dfs2(*it);
}
}
inline void kosaraju()
{
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
dfs2(i);
++solcur;
}
}
}
inline void afisare()
{
printf("%d\n",solcur);
for(int i=0;i<solcur;i++)
{
for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();++it) printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
citire();
topological();
kosaraju();
afisare();
}