Pagini recente » Cod sursa (job #1892028) | Cod sursa (job #2127895) | Cod sursa (job #1534971) | Cod sursa (job #925385) | Cod sursa (job #1142789)
#include<fstream>
using namespace std;
ifstream fcin("ctc.in");
ofstream fcout("ctc.out");
class graf
{
int noduri,muchii;
int *c,**a;
class nod
{
public:
int info;
nod *urm;
};
nod *n;
public:
graf()
{
noduri=0;
muchii=0;
}
void citire()
{
int i,x,y;
fcin>>x>>y;
noduri=x;
muchii=y;
nod *poz[noduri+1],*p;
n=new nod[noduri+1];
c=new int[noduri+1];
a=new int*[noduri+1];
for(i=1;i<=noduri;i++)
{
a[i]=new int[noduri+1];
n[i].info=0;
n[i].urm=NULL;
poz[i]=&n[i];
}
for(i=1;i<=muchii;i++)
{
fcin>>x>>y;
p=new nod;
p->info=y;
p->urm=NULL;
poz[x]->urm=p;
poz[x]=p;
}
}
void renew()
{
for(int i=1;i<=noduri;i++)
n[i].info=0;
}
void df(int x)
{
nod *p;
fcout<<x<<' ';
n[x].info=1;
p=&n[x];
while(p->urm!=NULL)
{
p=p->urm;
if(n[p->info].info==0)
df(p->info);
}
}
void bf(int x)
{
renew();
int t=1,u=1;
nod *p;
c[1]=x;
n[x].info=1;
while(t<=u)
{
p=&n[c[t]];
while(p->urm!=NULL)
{
p=p->urm;
if(n[p->info].info==0)
{
c[++u]=p->info;
n[p->info].info=n[c[t]].info+1;
}
}
t++;
}
}
void afisbf()
{
int p,t;
p=1;
for(t=1;t<=noduri;t++)
if(p==n[c[t]].info)
fcout<<c[t]<<' ';
else
{
p=n[c[t]].info;
fcout<<'\n'<<c[t]<<' ';
}
}
void matrice()
{
int i,t=1,u=1;
for(i=1;i<=noduri;i++)
{
bf(i);
for(t=1;t<=noduri;t++)
a[i][t]=n[t].info-1;
}
}
void afism()
{
int i,t;
for(i=1;i<=noduri;i++)
{
for(t=1;t<=noduri;t++)
fcout<<a[i][t]<<' ';
fcout<<'\n';
}
}
void conex()
{
int i,t=1,u=1;
matrice();
c[1]=1;c[0]=1;
for(i=2;i<=noduri;i++)
{
int t=1,j;
for(j=i-1;j>=1;j--)
if(a[i][j]!=-1&&a[j][i]!=-1)
{
c[i]=c[i-1];
t=0;
}
if(t==1)
{c[i]=i;c[0]++;}
}
}
void afiscon()
{
int i,t=c[1];
fcout<<c[0]<<'\n';
fcout<<t<<' ';
for(i=2;i<=noduri;i++)
{
if(c[i]==t)
fcout<<i<<' ';
else
{
fcout<<'\n'<<i<<' ';
t=c[i];
}
}
}
};
int main()
{
graf t;
t.citire();
t.conex();
t.afiscon();
return 0;
}