Pagini recente » Cod sursa (job #670932) | Cod sursa (job #1100330) | Cod sursa (job #2709059) | Cod sursa (job #132400) | Cod sursa (job #812034)
Cod sursa(job #812034)
#include<cstdio>
#include<cstdlib>
using namespace std;
int* gr[100001];
int* grt[100001];
int* ctc[100001];
bool viz[100001];
int postord[100001];
void dfs(int vf)
{
int i;
viz[vf]=1;
for(i=1;i<=gr[vf][0];i++)
if(!viz[gr[vf][i]])
dfs(gr[vf][i]);
postord[0]++;
postord[postord[0]]=vf;
}
void dfst(int vf, int nct)
{
int i;
viz[vf]=0;
ctc[nct][0]++;
ctc[nct]=(int*)realloc(ctc[nct],(ctc[nct][0]+1)*4);
ctc[nct][ctc[nct][0]]=vf;
for(i=1;i<=grt[vf][0];i++)
if(viz[grt[vf][i]])
dfst(grt[vf][i],nct);
}
int main()
{
int n,m,i,x,y,nct=0,j;
freopen("ctc.in","r",stdin);
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)
{
gr[i]=(int*)realloc(gr[i],4);
grt[i]=(int*)realloc(grt[i],4);
gr[i][0]=0;grt[i][0]=0;
}
for(i=1;i<=m;i++)
{
scanf("%d %d\n",&x,&y);
gr[x][0]++;
gr[x]=(int*)realloc(gr[x],(gr[x][0]+1)*4);
gr[x][gr[x][0]]=y;
grt[y][0]++;
grt[y]=(int*)realloc(grt[y],(grt[y][0]+1)*4);
grt[y][grt[y][0]]=x;
}
fclose(stdin);
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
for(i=n;i>0;i--)
if(viz[postord[i]])
{
nct++;
ctc[nct]=(int*)realloc(ctc[nct],4);
ctc[nct][0]=0;
dfst(postord[i],nct);
}
freopen("ctc.out","w",stdout);
printf("%d\n",nct);
for(i=1;i<=nct;i++)
{
for(j=1;j<=ctc[i][0];j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
/*for(i=1;i<=postord[0];i++)
g<<postord[i]<<" ";
g<<'\n';*/
fclose(stdout);
return 0;
}
/*#include<fstream>
using namespace std;
int* gr[100001];
int* grt[100001];
int* ctc[100001];
bool viz[100001];
int postord[100001];
void dfs(int vf)
{
int i;
viz[vf]=1;
for(i=1;i<=gr[vf][0];i++)
if(!viz[gr[vf][i]])
dfs(gr[vf][i]);
postord[0]++;
postord[postord[0]]=vf;
}
void dfst(int vf, int nct)
{
int i;
viz[vf]=0;
ctc[nct][0]++;
ctc[nct]=(int*)realloc(ctc[nct],(ctc[nct][0]+1)*4);
ctc[nct][ctc[nct][0]]=vf;
for(i=1;i<=grt[vf][0];i++)
if(viz[grt[vf][i]])
dfst(grt[vf][i],nct);
}
int main()
{
int n,m,i,x,y,nct=0,j;
ifstream f("ctc.in");
f>>n>>m;
for(i=1;i<=n;i++)
{
gr[i]=(int*)realloc(gr[i],4);
grt[i]=(int*)realloc(grt[i],4);
gr[i][0]=0;grt[i][0]=0;
}
for(i=1;i<=m;i++)
{
f>>x>>y;
gr[x][0]++;
gr[x]=(int*)realloc(gr[x],(gr[x][0]+1)*4);
gr[x][gr[x][0]]=y;
grt[y][0]++;
grt[y]=(int*)realloc(grt[y],(grt[y][0]+1)*4);
grt[y][grt[y][0]]=x;
}
f.close();
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
for(i=n;i>0;i--)
if(viz[postord[i]])
{
nct++;
ctc[nct]=(int*)realloc(ctc[nct],4);
ctc[nct][0]=0;
dfst(postord[i],nct);
}
ofstream g("ctc.out");
g<<nct<<'\n';
for(i=1;i<=nct;i++)
{
for(j=1;j<=ctc[i][0];j++)
g<<ctc[i][j]<<" ";
g<<'\n';
}
g.close();
return 0;
}
*/