Pagini recente » Cod sursa (job #2910688) | Cod sursa (job #1479611) | Cod sursa (job #2504679) | Cod sursa (job #890165) | Cod sursa (job #2115605)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
struct nod{
int vecin;
struct nod *urm;
}*L[100003],*l[100003],*actual;
int st[100004];
int vf;
int viz[100004];
void dfs(int k,int nr,bool ok)
{
if(nr==1)
{
struct nod *t;
viz[k]=1;
for(t=l[k];t!=NULL;t=t->urm)
{
if(viz[t->vecin]==0)
dfs(t->vecin,nr,ok);
}
vf++;
st[vf]=k;
}
else
{
if(ok)
g<<k<<" ";
struct nod *t;
viz[k]=1;
for(t=L[k];t!=NULL;t=t->urm)
{
if(viz[t->vecin]==0)
dfs(t->vecin,nr,ok);
}
}
}
int main()
{
int x,y;
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>x>>y;
actual=new nod;
actual->vecin=y;
actual->urm=l[x];
l[x]=actual;
actual=new nod;
actual->vecin=x;
actual->urm=L[y];
L[y]=actual;
}
int nr=1;
bool ok=false;
vf=0;
//parcurgere in latime pentru a determina nodurile vizitate in ordinea lor de vizitare
for(int i=1;i<=n;i++)
if(viz[i]==0)
dfs(1,nr,ok);
//reinit viz
for(int i=1;i<=n;i++)
viz[i]=0;
//luam elem din stiva si parcurgem pe graful transpus
int nrctc=0;
nr=2;//parcurgerea pe mat transpusa
int aux=vf;
while(aux>0)
{
if(viz[st[aux]]==0)
{
dfs(st[aux],nr,ok);
nrctc++;
}
aux--;
}
g<<nrctc<<"\n";
for(int i=1;i<=n;i++)
viz[i]=0;
ok=true;
while(vf>0)
{
if(viz[st[vf]]==0)
{
dfs(st[vf],nr,ok);
g<<"\n";
}
vf--;
}
return 0;
}