Cod sursa(job #339410)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 9 august 2009 18:05:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#define Nmax 100005
#define push_back pb
#include <vector>
using namespace std;

bool use[Nmax];
vector <int> v[Nmax];
int n,m,nr;

void citire(){
	int i,x,y;
   freopen("dfs.in","r",stdin);
   freopen("dfs.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(i=1;i<=m;++i){
   	scanf("%d%d",&x,&y);
      v[x].pb(y);
      v[y].pb(x);
   }
}

void dfs(int k){
   vector<int>:: iterator it;
	use[k] = 1;
   for(it=v[k].begin(); it != v[k].end(); it++)
     if(!use[*it]) dfs(*it);
}

int main(){
   int i;
	citire();

   for(i=1;i<=n;++i)
     if(!use[i]){
                 dfs(i);
                 nr++;
     }

   printf("%d\n",nr);
   fclose(stdin); fclose(stdout);
   return 0;
}