Cod sursa(job #1094335)

Utilizator BLz0rDospra Cristian BLz0r Data 29 ianuarie 2014 11:44:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <cstdio>
#include <vector>
using namespace std;

FILE *f=fopen ("dfs.in","r");
FILE *g=fopen ("dfs.out","w");

vector<int>v[100005];
int n,m,lg[100005];
bool ap[100005];

void dfs(int nod){
	ap[nod]=1;
	for (int i=0;i<lg[nod];++i){
		if (!ap[v[nod][i]]){
			dfs(v[nod][i]);
		}
	}
}

int main(){
	int s=0,x,y;
	
	fscanf (f,"%d%d",&n,&m);
	for (int i=1;i<=m;++i){
		fscanf (f,"%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	for (int i=1;i<=n;++i) lg[i]=v[i].size();
	
	for (int i=1;i<=n;++i){
		if (!ap[i]){
			s++;
			dfs(i);
		}
	}
	
	fprintf (g,"%d",s);
	
	return 0;
}