Cod sursa(job #943439)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 25 aprilie 2013 14:35:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <vector>
#define nmax 100005
using namespace std;
 

vector <int> v[nmax];
int n,m;
bool viz[nmax];
int componente;

void fill(int a) {
    viz[a] = true;
    int s = v[a].size();
    for (int i=0;i<s;i++) {
    	if (!viz[v[a][i]]) 
			fill(v[a][i]);
    }
}

int main() {
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i=1;i<=n;i++) if (!viz[i]) {
        componente++;
        fill(i);
    }
    printf("%d\n",componente);
    return 0;
}