Pagini recente » Cod sursa (job #3130825) | Cod sursa (job #707573) | Cod sursa (job #1040637) | Cod sursa (job #161694) | Cod sursa (job #2756724)
#include <cstdio>
#include <cstdlib>
#define N 100001
int *a[N];
int n;
int use[N];
inline void dfs(int n)
{
// Daca e vizitat return, altfel, viziteaza-l
if(use[n]) return ;
use[n]=1;
int i;
for(i=1;i<=a[n][0];++i)
// trece prin toti vecinii, si daca nu e vizitat, il vizitez si fac toti vecinii de acolo
if(!use[a[n][i]])
dfs(a[n][i]);
}
int main()
{
int m,p,q;
freopen("dfs.in","r",stdin);
scanf("%d %d\n", &n, &m);
for(int i=1;i<=n;++i) a[i]=new int[2], a[i][0]=0;
// citesc o muchie
while(m--)
{
scanf("%d %d\n", &p, &q);
// mai adaug doua elemente in vectorul de muchii ( e o lista )
// vectorii din stl cand se umplu isi dubleaza memoria
// a[p] : lista de vecini a nodului p
a[p]=(int*)realloc(a[p], sizeof(int)*(a[p][0]+2));
a[q]=(int*)realloc(a[q], sizeof(int)*(a[q][0]+2));
// a[p][0] va contine numarul de elemente din a[p]
// OBS: Graf neorientat: adaug al fiecare pe celalalt
a[p][++a[p][0]]=q;
a[q][++a[q][0]]=p;
}
int nr=0;
for(int i=1;i<=n;++i)
// daca nodul nu a fost vizitat, atunci il vizitez si ii fac dfs
// daca intalnesc iar un nod nevizitat, ala e un nod dintr-o alta componenta conexa
if(!use[i]){++nr; dfs(i);}
freopen("dfs.out","w",stdout);
printf("%d\n", nr);
return 0;
}