Pagini recente » Cod sursa (job #2421944) | Cod sursa (job #2885821) | Cod sursa (job #1807460) | Cod sursa (job #1406639) | Cod sursa (job #1113813)
#include <fstream>
using namespace std;
ifstream f("date.in");
ofstream g("date.ok");
long int i,j,m,n,x,y,k;
int a[20000][20000];
int suc[10000],viz[10000];
int pred[10000],comb[10000],nr;
void mm(int v[10000])
{int i;
for(i=1;i<=n;i++) v[i]=0;
}
void succesor(int nod)
{int i;
viz[nod]=1;suc[nod]=1;
for(i=1;i<=n;i++)
if(a[nod][i]==1 && viz[i]==0) {succesor(i);
k++;}
}
void predecesor(int nod)
{int i;
viz[nod]=1;pred[nod]=1;
for(i=1;i<=n;i++)
if(a[i][nod]==1 && viz[i]==0){ predecesor(i);
k++;}
}
void combin(int suc[100],int pred[100],int comb[100])
{int i,j;
nr++;
for(i=1;i<=n;i++)
if(suc[i]==1 && pred[i]==1&&comb[i]==0) comb[i]=nr;;
}
void afis(int comb[100])
{int i,j;
g<<nr<<endl;
for(i=1;i<=nr;i++)
{
for(j=1;j<=n;j++)
if(comb[j]==i)g<<j<<' ';
g<<endl;
}
}
int main()
{int i;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y; a[x][y]=1;}
for(i=1;i<=n;i++)
{k=0;
mm(viz);
mm(suc);
mm(pred);
if(comb[i]==0)
{succesor(i);
mm(viz);
predecesor(i);
if(k) combin(suc,pred,comb);
}
}
afis(comb);
f.close();
g.close();
}