Cod sursa(job #237504)

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

vector <int> a[N];
deque <int> Q;
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.push_back(w);
     fol[w]=1;
     while (Q.size()!=0){
          x=Q[0];
          for (j=0;j<a[x].size();j++)
             if (!fol[a[x][j]]){
                fol[a[x][j]]=1;
                Q.push_back(a[x][j]);
             }
          Q.pop_front();
     }
}

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;
}