Pagini recente » Cod sursa (job #3224577) | Cod sursa (job #260886) | Cod sursa (job #3259785) | Cod sursa (job #285316) | Cod sursa (job #363183)
Cod sursa(job #363183)
#include<fstream>
#define nmax 5001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int l[nmax][nmax],n,m,a[nmax][nmax],numar=1;
int nr,viz[nmax],postordine[nmax];
int comp[nmax];
void citire()
{int i,m,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{fin>>x>>y;
l[x][0]++;
l[x][l[x][0]]=y;
a[y][0]++;
a[y][a[y][0]]=x;
}
}
void dfs(int x)
{int i;
viz[x]=1;
for(i=1;i<=l[x][0];i++)
if(viz[l[x][i]]==0)
dfs(l[x][i]);
postordine[++nr]=x;
}
void dfst(int x)
{int i;
viz[x]=0;
comp[x]=numar;
for(i=1;i<=a[x][0];i++)
if(viz[a[x][i]]==1)
dfst(a[x][i]);
}
int main()
{int i,j;
citire();
for(i=1;i<=n;i++)
if(viz[i]==0) dfs(i);
for(i=n;i>=1;i--)
if(viz[postordine[i]])
{dfst(postordine[i]);
numar++;
}
fout<<numar-1<<'\n';
for(j=1;j<=numar;j++)
{for(i=1;i<=n;i++)
if(comp[i]==j)
fout<<i<<' ';
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}