Pagini recente » Cod sursa (job #2495558) | Cod sursa (job #2084821) | Cod sursa (job #327982) | Cod sursa (job #2723254) | Cod sursa (job #2478275)
#include <cstdio>
#include <vector>
using namespace std;
vector <int> graf[100003];
vector <int> grafinv[100003];
vector <int> tarec[100003];
vector <int> stiva;
int n,m,cnt,vizitat[100003];
void dfs (int nod)
{
vizitat[nod]=1;stiva.push_back(nod);
for(int i=0;i<(int)graf[nod].size();++i)
if(vizitat[graf[nod][i]]==0)
dfs(graf[nod][i]);
}
void dfs1 (int nod)
{
vizitat[nod]=0;tarec[cnt].push_back(nod);
for(int i=0;i<(int)grafinv[nod].size();++i)
if(vizitat[grafinv[nod][i]]==1)
dfs1(grafinv[nod][i]);
}
void ctc_kosaraju ()
{
for(int i=1;i<=n;++i)
if(vizitat[i]==0)
dfs(i);
while(stiva.size()!=0)
{
if(vizitat[stiva[stiva.size()-1]]==1)
dfs1(stiva[stiva.size()-1]);
stiva.pop_back();++cnt;
}
}
int main ()
{
int nr1,nr2;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d", &n, &m);
for(int i=1;i<=m;++i)
{
scanf("%d%d", &nr1, &nr2);
graf[nr1].push_back(nr2);grafinv[nr2].push_back(nr1);
}
ctc_kosaraju();
printf("%d\n", cnt);
for(int i=0;i<cnt;++i)
{
for(int i1=0;i1<(int)tarec[i].size();++i1)
printf("%d ", tarec[i][i1]);
printf("\n");
}
return 0;
}