Pagini recente » Cod sursa (job #2508920) | Cod sursa (job #2315603) | Cod sursa (job #775389) | Cod sursa (job #280777) | Cod sursa (job #606275)
Cod sursa(job #606275)
#include<fstream>
using namespace std;
struct nod{int info;nod *adr;}*v[100001],*v2[100001],*p,*cp1[100001],*cp2[100002];
int n,m,i,x,y,pred[100002],suc[100002],nrc,j;
void dfs_pred(int nod)
{
pred[nod]=nrc;
while(v2[nod])
{
if(!pred[v2[nod]->info]) dfs_pred(v2[nod]->info);
v2[nod]=v2[nod]->adr;
}
}
void dfs_suc(int nod)
{
suc[nod]=nrc;
while(v[nod])//parcurgere pe coloana(a 2-a lista)
{
if(!suc[v[nod]->info]) dfs_suc(v[nod]->info);
v[nod]=v[nod]->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;
}
for(i=1;i<=n;i++) {cp1[i]=v[i]; cp2[i]=v2[i];}
nrc=1;
for(i=1;i<=n;i++)
if(suc[i]==0)
{
dfs_suc(i); v[i]=cp1[i];
dfs_pred(i); v2[i]=cp2[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;}