Pagini recente » Cod sursa (job #2909897) | Cod sursa (job #772144) | Cod sursa (job #1501067) | Cod sursa (job #389039) | Cod sursa (job #1249769)
#include <fstream>
#define DMAX 5000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire();
void rezolvare();
//void DFS(int vf,int uz[],int matr[][DMAX]);
void DFSA(int vf);
void DFST(int vf);
void get_ctc();
void clear();
void afisare();
int A[DMAX][DMAX];
int T[DMAX][DMAX];
int sol[DMAX][DMAX];
int uz1[DMAX], uz2[DMAX], uzt[DMAX];
int n,m,nrctc;
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
void citire()
{
int i,x,y;
fin>>n>>m;
for (i=1;i<=m;i++)
{
fin>>x>>y;
A[x][0]++;
A[x][ A[x][0] ]=y;
T[y][0]++;
T[y][ T[y][0] ]=x;
}
}
void rezolvare()
{
int i;
for (i=1;i<=n;i++)
if (uzt[i]==0)
{
//DFS(i,uz1,A);
//DFS(i,uz2,T);
DFSA(i);
DFST(i);
get_ctc();
clear();
}
}
void get_ctc()
{
int i,j;
for (i=1;i<=n;i++)
if (uz1[i]==(uz2[i]==1))
{
nrctc++;
//fout<<"Componenta tare conexa numarul "<<nrctc<<": ";
for (j=i;j<=n;j++)
if (uz1[j]==(uz2[j]==1))
{
uzt[j]=1;
sol[nrctc][ ++sol[nrctc][0] ]=j;
// fout<<j<<' ';
}
//fout<<'\n';
return;
}
}
void clear()
{
int i;
for (i=1;i<=n;i++) uz1[i]=uz2[i]=0;
}
void DFSA(int vf)
{
int i;
uz1[vf]=1;
for (i=1;i<=A[vf][0];i++)
if ( uz1[ A[vf][i] ]==0 ) DFSA(A[vf][i]);
}
void DFST(int vf)
{
int i;
uz2[vf]=1;
for (i=1;i<=T[vf][0];i++)
if ( uz2[ T[vf][i] ]==0 ) DFST(T[vf][i]);
}
void afisare()
{
int i,j;
fout<<nrctc<<'\n';
for (i=1;i<=nrctc;i++)
{for (j=1;j<=sol[i][0];j++)
fout<<sol[i][j]<<' ';
fout<<'\n';
}
}