Pagini recente » Cod sursa (job #3259662) | Cod sursa (job #1847467) | Cod sursa (job #365124) | Cod sursa (job #1592160) | Cod sursa (job #281991)
Cod sursa(job #281991)
#include<stdio.h>
#define N 100000
int n,m;
bool viz[N];
struct nod
{
int info;
nod *adr;
};
nod *v[N];
void adauga(nod *&vf,int x)
{
nod *q=new nod;
q->info=x;
q->adr=vf;
vf=q;
}
void citire()
{
int x,y;
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%d%d", &x, &y);
adauga(v[x],y);//adauga y in lista vecinilor lui x
adauga(v[y],x);
}
}
/*
void afisare(nod *p)
{
while(p)
{
printf("%d ",p->info);
p=p->adr;
}
printf("\n");
}
*/
void dfs(int x)
{
int y;
nod *aux=v[x];
viz[x]=true;
while(aux)
{
y=aux->info;
if(!viz[y])
dfs(y);
aux=aux->adr;
}
}
int main()
{
int nr=0;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
for(int i=1;i<=n;i++)
afisare(v[i]);
for(int i=1;i<=n;i++)
{
if(!viz[i])
{
dfs(i);
nr++;
}
}
printf("%d",nr);
return 0;
}