Pagini recente » Cod sursa (job #1593474) | Cod sursa (job #1097039) | Cod sursa (job #1150186) | Cod sursa (job #2862160) | Cod sursa (job #606251)
Cod sursa(job #606251)
#include<fstream>
using namespace std;
struct nod{int info;nod *adr;}*v[100001],*v2[100001],*p;
int n,m,i,x,y,pred[100002],suc[100002],nrc,j;
void dfs_pred(int nod)
{ p=v[nod];
pred[nod]=nrc;
while(p)
{
if(!pred[p->info]) dfs_pred(p->info);
if(p)p=p->adr;
}
}
void dfs_suc(int nod)
{ p=v2[nod];
suc[nod]=nrc;
while(p)//parcurgere pe coloana(a 2-a lista)
{
if(!suc[p->info]) dfs_suc(p->info);
if(p)p=p->adr;
}
}
int main()
{
ifstream f("ctc.in");ofstream g("ctc.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
p=new nod;
p->info=y; p->adr=v[x]; v[x]=p;
p=new nod;
p->info=x; p->adr=v2[y]; v2[y]=p;
}
nrc=1;
for(i=1;i<=n;i++)
if(suc[i]==0)
{
dfs_suc(i);
dfs_pred(i);
for(j=1;j<=n;j++)
if(suc[j]!=pred[j]) suc[j]=pred[j]=0;
nrc++;
}
g<<nrc-1<<"\n";
for(i=1;i<nrc;i++)
{
for(j=1;j<=n;j++)
if(pred[j]==i && suc[j]==i) g<<j<<" ";
g<<"\n";
}
f.close();g.close();
return 0;}