Cod sursa(job #1340200)

Utilizator cociorbaandreiAndrei Cociorba cociorbaandrei Data 11 februarie 2015 17:39:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <vector>
#include "stdio.h"
using namespace std;
int n, m, viz[100005], c;
std::vector<vector<int> > listaVecini(100005);

void dfs(int x){
	viz[x] = 1;
	for (std::vector<int>::iterator itr = listaVecini[x].begin(); itr != listaVecini[x].end();++itr)
		if(viz[*itr] == 0) dfs(*itr);
}
int main()
{
	/* code */
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);


	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
	{
		int t1, t2;
		scanf("%d%d",&t1,&t2);
		listaVecini[t1].push_back(t2);
		listaVecini[t2].push_back(t1);
	}
	for(int i = 1;i <= n;i++){
		if(viz[i] == 0){
			c++;
			dfs(i);
		}
	}
	printf("%d\n", c);
	return 0;
}