Cod sursa(job #2756724)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 2 iunie 2021 17:41:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#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;
}