Cod sursa(job #530337)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 7 februarie 2011 16:24:06
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <math.h>
#define N 100005

using namespace std;

struct Nod {
    int v;
    Nod* next;
};
int n,m;
int x,y;
int viz[N];
Nod* gr[N];

void insert(Nod *&p, int vl) {
    Nod* op = new Nod();
    op->next = p;
    op->v = vl;
    p = op;
}
void dfs(int p) {
    viz[p] = 1;
    for(Nod* it = gr[p]; it != 0; it = it -> next)
     if (!viz[it->v])
      dfs(it->v);
}
int main() {
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i = 1; i <= m; i++) {
       scanf("%d %d",&x,&y);
       insert(gr[x],y);
       insert(gr[y],x);
    }
    int cnt = 0;
    for(int i = 0; i <= n; i++)
     if (!viz[i]) {
         cnt++;
         dfs(i);
     }
    printf("%d\n",cnt);
    return 0;
}