Pagini recente » Cod sursa (job #469519) | Cod sursa (job #934421) | Cod sursa (job #1962442) | Cod sursa (job #2767258) | Cod sursa (job #739439)
Cod sursa(job #739439)
#include<fstream>
#include<stdlib.h>
#define nmax 50010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int i, j, n , m, *A[nmax], *B[nmax], *C[nmax];
int viz[nmax], ord[nmax], nr , gr;
int x, y, k;
void DFS(int x)
{
int i ;
viz[x] = 1;
for(i = 1 ; i <= A[x][0] ; i++)
if(viz[A[x][i]]==0)
DFS(A[x][i]);
ord[++nr] = x;
}
void DFST(int x)
{
int i;
viz[x] = 0;
C[gr][0]++;
C[gr][C[gr][0]] = x;
for(i = 1; i <= B[x][0] ;i++)
if(viz[B[x][i]]==1)
DFST(B[x][i]);
}
void read()
{
int i, k ;
fin >> n >>m ;
for(i = 1; i <= n;i++)
{
A[i] = (int *) realloc(A[i], sizeof(int));
A[i][0] = 0 ;
B[i] = (int *) realloc(B[i], sizeof(int));
B[i][0] = 0;
C[i] = (int *) realloc(C[i], sizeof(int));
C[i][0]= 0;
}
for(k = 1 ; k <= m ;k++)
{
fin >>i >>j ;
A[i][0] ++;
A[i] = (int *) realloc(A[i], (A[i][0] + 1)* sizeof(int));
A[i][A[i][0]] = j;
B[j][0]++;
B[j] = (int *) realloc(B[j], (B[j][0] + 1 )* sizeof(int));
B[j][B[j][0]] = i;
}
for(i = 1; i <= n;i++)
if(viz[i] ==0 )
DFS(i);
for(i = n; i ; i--)
if(viz[ord[i]])
{
gr++;
DFST(ord[i]);
}
}
void display()
{
int i, j ;
fout << gr <<'\n';
for(i = 1; i <= gr; i++)
{
for(j = 1; j <= C[i][0]; j++)
fout<< C[i][j] <<" ";
fout <<'\n' ;
}
}
int main()
{
read();
display();
fin.close();
fout.close();
return 0;
}