Cod sursa(job #2668331)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 4 noiembrie 2020 19:42:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb

#include <cstdio>
#include <cstdlib>
#define N 100001

int *a[N];
int n;
int use[N];

inline void dfs(int n)
{
    if(use[n]) return ;
    use[n]=1;

    int i;
    for(i=1;i<=a[n][0];++i)
        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;

    while(m--)
    {
        scanf("%d %d\n", &p, &q);
        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][++a[p][0]]=q;
        a[q][++a[q][0]]=p;


    }
    int nr=0;
    for(int i=1;i<=n;++i)
        if(!use[i]){++nr; dfs(i);}

    freopen("dfs.out","w",stdout);
    printf("%d\n", nr);
    return 0;
}