Pagini recente » Cod sursa (job #2898220) | Cod sursa (job #1982578) | Cod sursa (job #1545505) | Cod sursa (job #1080308) | Cod sursa (job #2516242)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m;
int vf[200001],urm[200001],last[100001],nr;
int vfT[200001],urmT[200001],lastT[100001],nrT;
bitset <100001> viz,vizT;
int ord[100001],nrO;
vector <int> comp[100001];
int all;
void adauga(int nod,int vec)
{
vf[++nr]=vec;
urm[nr]=last[nod];
last[nod]=nr;
}
void adaugaT(int nod,int vec)
{
vfT[++nrT]=vec;
urmT[nrT]=lastT[nod];
lastT[nod]=nrT;
}
void dfs(int nod)
{
viz[nod]=1;
for(int k=last[nod];k;k=urm[k])
if(!viz[ vf[k] ])
dfs(vf[k]);
ord[++nrO]=nod;
}
void dfsT(int nod)
{
vizT[nod]=1;
comp[all].push_back(nod);
for(int k=lastT[nod];k;k=urmT[k])
if(!vizT[ vfT[k] ])
dfsT(vfT[k]);
}
int main()
{
in>>n>>m;
for(int i,j,k=1;k<=m;k++)
{
in>>i>>j;
adauga(i,j);
adaugaT(j,i);
}
for(int i=1;i<=n;i++)
if(!viz[i])
dfs(i);
for(int i=n;i>=1;i--)
if(!vizT[ ord[i] ])
{
all++;
dfsT(ord[i]);
}
out<<all<<'\n';
for(int i=1;i<=all;i++)
{
for(int j=0;j<comp[i].size();j++)
out<<comp[i][j]<<' ';
out<<'\n';
}
return 0;
}