Pagini recente » Cod sursa (job #1825510) | Cod sursa (job #2356172) | Cod sursa (job #2189188) | Cod sursa (job #963817) | Cod sursa (job #1526322)
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> g[100010],gt[100010],components[100010];
int seen[100010],order[100010],cnt,comp;
void dfs(int node){
int i,dim=g[node].size();
seen[node]=1;
for(i=0;i<dim;i++)
if(seen[g[node][i]]==0)
dfs(g[node][i]);
cnt++;
order[cnt]=node;
}
void anti_dfs(int node){
int i,dim=gt[node].size();
seen[node]=1;
components[comp].push_back(node);
for(i=0;i<dim;i++)
if(seen[gt[node][i]]==0)
anti_dfs(gt[node][i]);
}
int main(int node){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m,a,b,i,dim,j;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
g[a].push_back(b);
gt[b].push_back(a);
}
cnt=comp=0;
for(i=1;i<=n;i++)
if(seen[i]==0)
dfs(i);
memset(seen,0,sizeof(seen));
for(i=n;i>=1;i--)
if(seen[order[i]]==0){
comp++;
anti_dfs(order[i]);
}
printf("%d\n",comp);
for(i=1;i<=comp;i++){
dim=components[i].size();
for(j=0;j<dim;j++){
printf("%d",components[i][j]);
if(j==dim-1)
printf("\n");
else
printf(" ");
}
}
return 0;
}