Pagini recente » Cod sursa (job #1268355) | Cod sursa (job #217781) | Cod sursa (job #2589533) | Cod sursa (job #1803554) | Cod sursa (job #2176191)
#include <cstdio>
#include <vector>
#include <stack>
#define pb push_back
using namespace std;
const int nmax=100004;
vector<int>adj[nmax],adjt[nmax],sols[nmax];
int n,p,vis[nmax],vis2[nmax];
stack<int>stk;
inline void citire()
{
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
adj[x].pb(y);
adjt[y].pb(x);
}
}
void dfs(int nod)
{
vis[nod]=1;
for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();++it)
{
if(!vis[*it]) dfs(*it);
}
stk.push(nod);
}
inline void topological()
{
for(int i=1;i<=n;i++)
{
if(!vis[i]) dfs(i);
}
}
void dfs2(int nod)
{
sols[p].pb(nod);
vis2[nod]=1;
for(vector<int>::iterator it=adjt[nod].begin();it!=adjt[nod].end();++it)
{
if(vis2[*it]==0) dfs2(*it);
}
}
inline void kosaraju()
{
while(!stk.empty())
{
int nod=stk.top();
stk.pop();
if(vis2[nod]==0) ++p,dfs2(nod);
}
}
inline void afis()
{
printf("%d\n",p);
for(int i=1;i<=p;i++)
{
for(vector<int>::iterator it=sols[i].begin();it!=sols[i].end();++it) printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
citire();
topological();
kosaraju();
afis();
}