Pagini recente » Cod sursa (job #2816961) | Cod sursa (job #916056) | Borderou de evaluare (job #1298045) | Cod sursa (job #953864) | Cod sursa (job #1607580)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int >g[100005],ord,com[100005],gb[100005];
int nrcom,n,m,viz[100005],asig[100005];
void citire()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)
{
int nod1,nod2;
scanf("%d%d",&nod1,&nod2);
g[nod1].push_back(nod2);
gb[nod2].push_back(nod1);
}
}
void dfs(int nod)
{
viz[nod]=1;
for (vector <int > :: iterator it=g[nod].begin();it!=g[nod].end();++it)
if (!viz[*it])
dfs(*it);
ord.push_back(nod);
}
void assig(int nod)
{
com[nrcom].push_back(nod);
asig[nod]=1;
for (vector <int > :: iterator it=gb[nod].begin();it!=gb[nod].end();++it)
if (!asig[*it])
assig(*it);
}
void kosaraju()
{
for (int i=1;i<=n;++i)
if (!viz[i])
dfs(i);
while (!ord.empty())
{
if (!asig[ord.back()])
{
assig(ord.back());
++nrcom;
}
ord.pop_back();
}
printf("%d\n",nrcom);
for (int i=0;i<nrcom;++i)
{
for (vector <int > :: iterator it=com[i].begin();it!=com[i].end();++it)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
kosaraju();
return 0;
}