Pagini recente » Cod sursa (job #401741) | Cod sursa (job #2563741) | Cod sursa (job #1846258) | Cod sursa (job #1726418) | Cod sursa (job #476716)
Cod sursa(job #476716)
#include<cstdio>
#include<bitset>
#include<vector>
using namespace std;
int i,n,m,sorta[100100],nr,j;
vector<int> a[100100];
vector<int> at[100100];
vector< vector<int> > rez;
bitset<100100> fol;
void dfs(int i)
{
fol[i]=1;
for(int j=0;j<a[i].size();++j)
if(!fol[a[i][j]]) dfs(a[i][j]);
sorta[++nr]=i;
}
void dfs2(int i)
{
fol[i]=0;
rez[rez.size()-1].push_back(i);
for(int j=0;j<at[i].size();++j)
if(fol[at[i][j]]) dfs2(at[i][j]);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
at[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!fol[i]) dfs(i);
vector<int> aux;
for(i=n;i>0;--i)
if(fol[ sorta[i] ])
{
rez.push_back(aux);
dfs2(sorta[i]);
}
printf("%d\n",rez.size());
for(i=0;i<rez.size();++i)
{
for(j=0;j<rez[i].size();++j) printf("%d ",rez[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}