Cod sursa(job #923109)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 23 martie 2013 00:20:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <vector>
#include <algorithm>
#include <stdio.h>
#define Nmax 100001
using namespace std;

vector<int> v[Nmax];
int viz[Nmax];
int n, m, nod;

void dfs(int nr)
{
	int i, j;
	viz[nr] = 1;
	for(vector<int>::iterator it = v[nr].begin(); it!=v[nr].end(); ++it)
		if(!viz[*it])
				dfs(*it);
}

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

	cnt = 0;
	for(i=1;i<=n;++i)
		if(!viz[i])
		{
			cnt++;
			dfs(i);
		}
		
	printf("%d\n", cnt);
}