Cod sursa(job #1729478)

Utilizator andreiSevastreAndrei Sevastre andreiSevastre Data 14 iulie 2016 20:16:39
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <vector>
#include <stdio.h>
#define N 100001
using namespace std;

vector<int>v[N];
int viz[100001];


int dfs (int nod)
{
	viz[nod]=1;
	
	for(int i=1; i<=v[nod].size(); i++)
	{
		if(viz[i]==0)
		{
			dfs(v[nod][i]);
		}
	}
}

int main ()
{
	int n,m,x,y,nr=0;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	scanf("%d%d", &n,&m);
	
	for(int i=1; i<=m; i++)
	{
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1; i<=n; i++)
	{
		if(!viz[i])
		{
			nr++;
			dfs(i);
		}
	}
	printf("%d", nr);
	/*for(int i=1; i<=n; i++)
	{
		printf("%d ", viz[i]);
	}*/
return 0;
}