Pagini recente » Cod sursa (job #703152) | Cod sursa (job #1543568) | Cod sursa (job #1359621) | Cod sursa (job #122821) | Cod sursa (job #179724)
Cod sursa(job #179724)
#include <fstream.h>
#define N 100010
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod {long info; nod *urm;};
long viz[N],comp=0,n,m;
nod *graf[N],*q,*p;
void insert(int i1,int i2)
{
nod *p;
p=new nod;
p->info=i1;
if(!graf[i2]){p->urm=0;graf[i2]=p;}
else{p->urm=graf[i2];graf[i2]=p;}
p=new nod;
p->info=i2;
if(!graf[i1]){p->urm=0;graf[i1]=p;}
else{p->urm=graf[i1];graf[i1]=p;}
}
void citire()
{
long x,y,i;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
insert(x,y);
}
for(i=1;i<=n;i++)
viz[i]=0;
}
void DF(int k)
{
long indice;
viz[k]=comp;
nod *z;
z=graf[k];
while (z)
{
indice=z->info;
if (!viz[indice])
DF(indice);
z=z->urm;
}
}
int main()
{
citire();
long i;
for(i=1;i<=n;i++)
if(!viz[i])
{
comp++;
DF(i);
}
fout<<comp;
return 0;
}