Cod sursa(job #1988779)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 4 iunie 2017 18:31:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#define NMAX 100001

using namespace std;

FILE *f = freopen("dfs.in", "r", stdin);
FILE *g = freopen("dfs.out", "w", stdout);

struct nod{
    int vecin;
    nod *urmator;
};

nod *a[NMAX]; ///vector de pointeri, fiecare element a[i] reprezinta 'capul' listei de vecini ai nodului i
int coada[NMAX], p, u, n, m;
bool viz[NMAX];

void insertBeginning(nod *& head, int val) {
    nod *tmp = new nod;
    tmp -> vecin = val;
    tmp -> urmator = head;
    head = tmp;
}

void afisare(nod *& head) {
    nod *tmp = head;
    while(tmp != NULL) {
        printf("%d ", tmp -> vecin);
        tmp = tmp -> urmator;
    }
}

void bfs(int start) {
    viz[start] = true;
    p = u = 1;
    coada[p] = start;
    while(p <= u) {
        int node = coada[p];
        nod *head = a[node];
        while(head != NULL) {
            if(!viz[head -> vecin]) {
                viz[head -> vecin] = true;
                u ++;
                coada[u] = head -> vecin;
            }
            head = head -> urmator;
        }
        p ++;
    }
}
void readData() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i<=m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        insertBeginning(a[x], y);
        insertBeginning(a[y], x);
    }
}
int main() {
    readData();
    /*for(int i = 1; i<=n; i++) {
        printf("Vecinii nodului %d sunt ", i);
        afisare(a[i]);
        printf("\n");
    }*/
    int nrC = 0;
    for(int i = 1; i<=n; i++)
    if(!viz[i]) {
        nrC ++;
        bfs(i);
    }
    printf("%d", nrC);
    return 0;
}