Cod sursa(job #2259166)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 13 octombrie 2018 09:53:11
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <cstdlib>
#define MaxN 100005
using namespace std;
int N, M, i, *A[MaxN];
bool Fq[MaxN];
int k=0;
void Citire();
void DFS(int i);
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    Citire();
    return 0;
}
void Citire(){
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i){
        A[i]=(int *)realloc(A[i], sizeof(int));
        A[i][0]=0;
    }
    for(i=1; i<=M; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        A[x][0]++;
        A[x]=(int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
        A[y][0]++;
        A[y]=(int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
        A[x][A[x][0]]=y;
        A[y][A[y][0]]=x;
    }
    for(i=1; i<=N; ++i){
        if(!Fq[i]){
            Fq[i]=1;
            DFS(i);
            k++;
        }
    }
    printf("%d", k);
    return;
}
void DFS(int i){
    int j;
    for(j=1; j<=N; ++j){
        if(!Fq[A[i][j]]){
            Fq[A[i][j]]=1;
            DFS(A[i][j]);
        }
    }
    return;
}