Pagini recente » Cod sursa (job #1383252) | Cod sursa (job #532794) | Cod sursa (job #869536) | Cod sursa (job #1798924) | Cod sursa (job #1643743)
#include<fstream>
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
FILE *f=fopen("ctc.in","r");
ofstream g("ctc.out");
int *AT[100005],*a[100005],m,n,x,y,nr_ctc,viz[100005],postord[100005],nr;
vector<int> componente[100005];
void DFS(int nod)
{ int i;
viz[nod]=1;
for (i=1;i<=a[nod][0];i++)
if (viz[a[nod][i]]==0)
DFS(a[nod][i]);
postord[++nr]=nod; }
void DFS_t(int nod)
{ int i;
viz[nod]=0;
componente[nr_ctc].push_back(nod);
for (i=1;i<=AT[nod][0];i++)
if (viz[AT[nod][i]]==1)
DFS_t(AT[nod][i]);}
int main()
{ int i,j;
fscanf(f,"%d %d",&n,&m);
for (i=1;i<=n;i++)
{ a[i]=(int*)realloc(a[i],sizeof(int));
AT[i]=(int*)realloc(AT[i],sizeof(int));
a[i][0]=AT[i][0]=0;}
for (i=1;i<=m;i++)
{fscanf(f,"%d %d",&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(AT[y],(AT[y][0]+1)*sizeof(int));
AT[y][AT[y][0]]=x;}
for (i=1;i<=n;i++)
if (viz[i]==0)
DFS(i);
for (i=n;i>=1;i--)
if (viz[postord[i]]==1)
{nr_ctc++;
DFS_t(postord[i]);}
g<<nr_ctc<<'\n';
for (i=1;i<=nr_ctc;i++)
{ for (j=0;j<componente[i].size();j++)
g<<componente[i][j]<<" ";
g<<'\n';}
return 0;}