Cod sursa(job #500503)

Utilizator adalLica Adela adal Data 12 noiembrie 2010 13:35:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <vector>
#include <stdio.h>
#include <string.h>

#define pb push_back 

using namespace std;

vector <int> L[100001];
int n, m, i, x, y, nrc;
bool sel[100001];

void dfs(int x){
vector <int> :: iterator it;	
  sel[x]=true;
  for(it=L[x].begin(); it!=L[x].end();it++)
	  if (!sel[*it])
		   dfs(*it);
}


void load(){
   scanf("%d %d\n", &n, &m);
   for (i=1; i<= m; i++){
   scanf("%d %d\n",&x, &y);
   L[x].pb(y);
   L[y].pb(x);
 }
 return;
}


int main(){
 freopen("dfs.in","r",stdin);
 freopen("dfs.out","w",stdout);
 load();
 memset(sel, false, sizeof(sel));
 nrc=0;
 for (i=1; i<=n; i++)
   if (!sel[i]){
     nrc++;
	 dfs(i);
  }	
   printf("%d\n", nrc);
return 0;
}