Pagini recente » Cod sursa (job #116047) | Cod sursa (job #2690831) | Cod sursa (job #1395755) | Cod sursa (job #628022) | Cod sursa (job #876030)
Cod sursa(job #876030)
#include <cstdio>
#include <stdlib.h>
using namespace std;
int n,m,k,nr;
int * V[100001];
int * Vt[100001];
int *M[100001];
int vizitat[100001],sol[100001];
void citesc(){
freopen("ctc.in","r",stdin);
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
V[i] = (int*) realloc(V[i],sizeof(int));
V[i][0] = 0;
Vt[i]= (int*) realloc(Vt[i],sizeof(int));
Vt[i][0] = 0;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
V[x][0]++;
V[x] = (int*)realloc(V[x],(V[x][0]+1)*sizeof(int));
V[x][V[x][0]] = y;
Vt[y][0]++;
Vt[y] = (int*)realloc(Vt[y],(Vt[y][0]+1)*sizeof(int));
Vt[y][Vt[y][0]] = x;
}
}
void DFS(int nod){
vizitat[nod] = 1;
for(int i=1;i<=V[nod][0];i++)
if(!vizitat[V[nod][i]])
DFS(V[nod][i]);
sol[++k] = nod;
}
void DFST(int nod){
vizitat[nod] = 0;
M[nr][0]++;
M[nr] = (int*)realloc(M[nr],(M[nr][0]+1)*sizeof(int));
M[nr][M[nr][0]] = nod;
for(int i=1;i<=Vt[nod][0];i++)
if(vizitat[Vt[nod][i]])
DFST(Vt[nod][i]);
}
int main(){
citesc();
freopen("ctc.out","w",stdout);
for(int i=1;i<=n;i++)
if(!vizitat[i])
DFS(i);
for(int i=n;i>0;i--)
if(vizitat[sol[i]]){
++nr;
M[nr] = (int*)realloc(M[nr],sizeof(int));
M[nr][0] = 0;
DFST(sol[i]);
}
printf("%d\n",nr);
for(int i =1;i<=nr;i++){
for(int j=1;j<=M[i][0];j++)
printf("%d ", M[i][j]);
printf("\n");
}
return 0;
}