Pagini recente » Cod sursa (job #544058) | Cod sursa (job #2485953) | Cod sursa (job #120772) | Cod sursa (job #2967701) | Cod sursa (job #2428946)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
#define infile "ctc.in"
#define outfile "ctc.out"
int n , nr ,nrc;
int *D[NMAX];
int z;
int *A[NMAX];
int *AT[NMAX];
int *postordine;
bool *viz;
void citire();
void DFS(int);
void DFST(int);
int main()
{
citire();
ofstream fout(outfile);
for(int i=1;i<=n;++i)
{
if(!viz[i])
DFS(i);
}
for(int i=nr;i>0;--i)
{
if(viz[postordine[i]])
{
++nrc;
D[nrc] = (int *) malloc(sizeof(int));
D[nrc][0]=0;
DFST(postordine[i]);
}
}
fout<<nrc<<endl;
for(int i=1;i<=nrc;++i)
{
for(int j=1;j<=D[i][0];++j)
fout<<D[i][j]<<' ';
fout<<endl;
}
}
void citire()
{
ifstream fin(infile);
int m , x , y;
fin>>n>>m;
postordine = (int *)malloc((n+1)*sizeof(int));
viz = (bool *)malloc((n+1)*sizeof(bool));
for(int i=1;i<=n;++i)
{
A[i] = (int *) malloc(sizeof(int));
A[i][0]= 0;
AT[i] =(int *) malloc(sizeof(int));
AT[i][0]= 0;
}
for(int i=0;i<m;++i)
{
fin>>x>>y;
A[x][0]++;
A[x] = (int *) realloc(A[x],(A[x][0]+1)*sizeof(int));
A[x][A[x][0]] = y;
AT[y][0]++;
AT[y] = (int *) realloc(AT[y],(AT[y][0]+1)*sizeof(int));
AT[y][AT[y][0]] = x;
}
}
void DFS(int x)
{
viz[x]=1;
for(int i=1;i<=A[x][0] ; ++i)
{
if(!viz[A[x][i]])
DFS(A[x][i]);
}
postordine[++nr]=x;
}
void DFST(int x)
{
viz[x]=0;
D[nrc][0]++;
D[nrc] =(int *) realloc(D[nrc],(D[nrc][0]+1)*sizeof(int));
D[nrc][D[nrc][0]] = x;
for(int i=1;i<=AT[x][0];++i)
{
if(viz[AT[x][i]])
DFST(AT[x][i]);
}
}