Cod sursa(job #2013505)

Utilizator lulian23Tiganescu Iulian lulian23 Data 21 august 2017 16:46:21
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

int n, m, viz[ 100 * 100 + 5 ], s;

typedef struct nod{
    int x;
    nod *a;
} *pNod;
pNod v[ 100 * 100 + 5 ];

void adaugare(pNod &dest, int v){
    pNod p;
    p = new nod;
    p -> x = v;
    p -> a = dest;
    dest = p;
}

void citire(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out", "w", stdout);
    scanf("%d, %d", &n, &m);
    int x, y;
    for (int i = 1; i <= m; i++){
        scanf("%d, %d", &x, &y);
        adaugare(v[ x ], y);
        adaugare(v[ y ], x);
    }
}

void parcurgere(int nod){
    pNod p;
    viz[ nod ] = 1;
    for (p = v[ nod ]; p != NULL; p = p -> a)
        if (viz[ p -> x ] == false)
         parcurgere(p -> x);
}

int main(){
    citire();
    for (int i = 1; i <= n; i++)
        if (viz[ i ] == false){
           ++s;
           parcurgere( i );
        }
    printf("%d\n", s);
}