Cod sursa(job #1012669)

Utilizator Alina_MariaMateescu Adina Lenuta Maria Alina_Maria Data 19 octombrie 2013 15:06:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int viz[100005], x, y, i, n, m, cnt;

typedef struct nod {
    int x;
    nod *addr;
}*pnod;

pnod v[100005];

void add(pnod &dest, int val){
    pnod p;
    p = new nod;
    p->x = val;
    p->addr = dest;
    dest = p;
}

void DFS (int N){
    pnod p = new nod;
    viz[N] = 1;
    for(p = v[N]; p != NULL; p = p -> addr)
        if (!viz[p->x])
            DFS(p->x);
}

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

void inchidere_fis() {
    fclose(stdin);
    fclose(stdout);
}

int main() {
    citire_fis();
    for(int i = 1; i <= n; i++)
        if(!viz[i]) {
            cnt++;
            DFS(i);
        }
    printf("%d", cnt);
    inchidere_fis();
    return 0;
}