Pagini recente » Cod sursa (job #2565176) | Cod sursa (job #2328938) | Cod sursa (job #2432468) | Cod sursa (job #38433) | Cod sursa (job #1249757)
#include <fstream>
#define NMAX 10004
#define DMAX 10
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
bool g[NMAX][DMAX], gt[NMAX][DMAX];
bool a[NMAX], at[NMAX];
bool uz[NMAX], ctc[NMAX];
int c[NMAX][NMAX], nrctc;
void citire();
void tareconex();
void dfs(int vf, bool d[NMAX][DMAX], bool a[NMAX]);
void afisare();
int main()
{
citire();
tareconex();
afisare();
return 0;
}
void citire()
{
int i, x, y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
g[x][y]=1;
gt[y][x]=1;
}
for(i=1;i<=n;i++)
g[i][i]=gt[i][i]=1;
}
void tareconex()
{
int i, j;
for(i=1;i<=n;i++)
if(!ctc[i])
{
ctc[i]=1;
++nrctc;
for(j=1;j<=n;j++)
a[j]=uz[j]=0;
a[i]=1; uz[i]=1;
dfs(i, g, a);
for(j=1;j<=n;j++)
at[j]=uz[j]=0;
at[i]=1; uz[i]=1;
dfs(i, gt, at);
for(j=1;j<=n;j++)
if(a[j]&&at[j])
{
ctc[j]=1;
c[nrctc][++c[nrctc][0]]=j;
}
}
}
void dfs(int vf, bool d[NMAX][DMAX], bool a[NMAX])
{
int i;
a[vf]=1;
uz[vf]=1;
for(i=1;i<=n;i++)
if(!uz[i] && d[vf][i])
dfs(i, d, a);
}
void afisare()
{
int i, j;
fout<<nrctc<<'\n';
for(i=1;i<=nrctc;i++)
{
for(j=1;j<=c[i][0];j++)
fout<<c[i][j]<<' ';
fout<<'\n';
}
}