Cod sursa(job #237502)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 29 decembrie 2008 21:56:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
#include<vector>
#define N 100001
using namespace std;

vector <int> a[N];
int fol[N],n,m,nr;

void citire(){
int i,x,y;
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

void df(int w){
int j;
     fol[w]=1;
     for (j=0;j<a[w].size();j++)
         if (!fol[a[w][j]])
            df(a[w][j]);
}

int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    citire();
    for (int i=1;i<=n;i++)
        if (!fol[i])
           df(i),nr++;
    printf("%d\n",nr);
    return 0;
}