Pagini recente » Cod sursa (job #798040) | Cod sursa (job #1577633) | Cod sursa (job #1649664) | Cod sursa (job #3254009) | Cod sursa (job #1370366)
#include<cstdio>
#include<vector>
using namespace std;
int cate,n,m,a,b,k;
vector<int>v[100001],v1[100001],cmp[100001];
bool viz[100001],viz2[100001];
int st[100001];
void dfs1(int nod){
viz[nod]=true;
for(int i=0;i<v[nod].size();i++)
if(viz[v[nod][i]]==false)
dfs1(v[nod][i]);
st[++k]=nod;
}
void dfs2(int nod){
viz2[nod]=true;
// printf("%d ",nod);
cmp[cate].push_back(nod);
for(int i=0;i<v1[nod].size();i++)
if(viz[v1[nod][i]]==true&&viz2[v1[nod][i]]==false)
dfs2(v1[nod][i]);
}
int main(){
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",&a,&b);
v[a].push_back(b);
v1[b].push_back(a);
}
cate=0;
for(int i=1;i<=n;i++)
if(viz[i]==false){
k=0;
dfs1(i);
for(int j=1;j<=n;j++)
viz2[j]=false;
for(int j=k;j>=1;j--){
if(viz2[st[j]]==false){
cate++;
dfs2(st[j]);
// printf("\n");
}
}
}
printf("%d\n",cate);
for(int i=1;i<=cate;i++){
for(int j=0;j<cmp[i].size();j++)
printf("%d ",cmp[i][j]);
printf("\n");
}
return 0;
}