Cod sursa(job #500521)

Utilizator George25Raduta George Cristian George25 Data 12 noiembrie 2010 15:04:17
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
# include <stdio.h>
# include <string.h>
# include <vector>
using namespace std;
vector<int> a[10002];
vector<int>::iterator it;
int i,j,n,m,x,y,nr;
bool sel[100002];

void dfs (int x){
    vector<int>::iterator it;
    sel[x]=true;
    for (it=a[x].begin(); it!=a[x].end(); it++){
        if (!sel[*it]) dfs (*it);
	}    
}
 
int main(){
	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);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	memset(sel,false,sizeof(sel));
	nr=0;
	for(i=1; i<=n; i++){
		if (sel[i]==false){
			nr++;
			dfs(i);
		}
	}
	printf ("%d \n",nr);
	return (0);
}