Cod sursa(job #237503)

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

vector <int> a[N];
int fol[N],q[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 bf(int w){
int j,x;
     q[0]=w;
     fol[w]=1;
     for (int i=0,u=0;i<=u;i++){
         x=q[i];
         for (j=0;j<a[x].size();j++)
             if (!fol[a[x][j]]){
                fol[a[x][j]]=1;
                q[++u]=a[x][j];
             }
     }
}

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