Cod sursa(job #1169521)

Utilizator robert_fanrRobert Banu robert_fanr Data 11 aprilie 2014 16:38:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n, nr, contor;
bool vizitat[100003];

typedef struct nod{
    int x;
    nod *next;
} *m;
m a[100003];

void adaugare(m &cap, int val) {
    m p = new nod;
    p -> x = val;
    p -> next = cap;
    cap = p;
}

void citire() {
    in >> n >> nr;
    int i;
    for (i=1; i<=nr; i++) {
        int x, y;
        in >> x >> y;
        adaugare(a[x], y);
        adaugare(a[y], x);
    }
}

void dfs(int x) {
    m p;
    vizitat[x] = true;
    for (p = a[x]; p != NULL; p = p->next)
    {
        if (!vizitat[p->x])
            dfs(p->x);
    }
}

void numarare() {
    int i;
    for (i=1; i<=n; i++)
        if (!vizitat[i]) {
            contor++;
            dfs(i);
        }
    out << contor;
}

int main()
{
    citire();
    numarare();
}