Pagini recente » Cod sursa (job #965169) | Cod sursa (job #567026) | Cod sursa (job #3281148) | Cod sursa (job #707386) | Cod sursa (job #245392)
Cod sursa(job #245392)
#include<fstream.h>
#include<stdlib.h>
#define nmax 100005
int *a[nmax],*at[nmax],*rez[nmax];
int pos[nmax],viz[nmax],n,m,nr,nrc;
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]);
pos[++nr]=x;
}
void dfst(int x)
{
viz[x]=0;
++rez[nrc][0];
rez[nrc]=(int*)realloc(rez[nrc],(rez[nrc][0]+1)*sizeof(int));
rez[nrc][rez[nrc][0]]=x;
for (int i=1;i<=a[x][0];++i)
if (viz[a[x][i]])
dfst(a[x][i]);
}
int main()
{
ifstream be ("ctc.in");
ofstream ki ("ctc.out");
be>>n>>m;
int i,x,y;
for ( i=1;i<=n;++i)
{
a[i]=(int*)realloc(a[i],sizeof(int));
a[i][0]=0;
at[i]=(int*)realloc(at[i],sizeof(int));
at[i][0]=0;
}
for ( i=1;i<=m;++i)
{
be>>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(a[y],(a[y][0]+1)*sizeof(int));
at[y][at[y][0]]=x;
}
for (i=1;i<=n;++i)
if (!viz[i])
dfs(i);
for (i=1;i<=n;++i)
{
if (viz[pos[i]])
{
++nrc;
rez[nrc]=(int*)realloc(rez[nrc],sizeof(int));
rez[nrc][0]=0;
dfst(pos[i]);
}
}
for (i=1;i<=nrc;++i)
{
for (int j=1;j<=rez[i][0];++j)
ki<<rez[i][j]<<' ';
ki<<'\n';
}
ki.close();
return 0;
}