Pagini recente » Cod sursa (job #72868) | Cod sursa (job #435988) | Cod sursa (job #601170) | Cod sursa (job #2670699) | Cod sursa (job #1639024)
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int x,y,viz[100005],n,m,*a[100005],*b[100005],v[100005],graf[100005],nn;
vector <int> G[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]);
v[nn--]=nod;}
void dfs1(int nod, int nr)
{int i;
graf[nod]=nr;
for (i=1;i<=a[nod][0];i++)
if (graf[a[nod][i]]==0)
dfs1(a[nod][i],nr);}
int main()
{ int i,j,en,nr;
f>>n>>m;
nn=n;
for (i=1;i<=n;i++)
{ a[i]=(int *)realloc(a[i],sizeof(int));
b[i]=(int *)realloc(b[i],sizeof(int));
a[i][0]=b[i][0]=0;}
for (i=1;i<=m;i++)
{ f>>x>>y;
a[x][0]++;
a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
b[y][0]++;
b[y]=(int *)realloc(b[y],(b[y][0]+1)*sizeof(int));
b[y][b[y][0]]=x;}
for (i=1;i<=n;i++)
if (viz[i]==0)
dfs(i);
nr=1;
en=n;
while (en)
{ if (graf[v[en]]==0)
{dfs1(v[en],nr);
nr++;}
en--;}
g<<nr-1<<'\n';
for (i=1;i<nr;i++)
{for (j=1;j<=n;j++)
if (graf[j]==i)
g<<j<<" ";
g<<'\n';}
return 0; }