Cod sursa(job #575221)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 8 aprilie 2011 03:17:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define N 100001
vector<int> g[N];
bool v[N];

void dfs(int k)
{	v[k]=true;
	for (int i=0;i<g[k].size();i++)
	{	if(!v[g[k][i]])
		{dfs(g[k][i]);
		}
	}	
}

int main ()
{	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	int n,m,a,b;
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++)
	{	scanf("%d %d",&a, &b);
		g[a].push_back(b);
		g[b].push_back(a);	
	}
	int nrc=0;
	for (int i=1;i<=n;i++)
	{	if(!v[i])
		{	dfs(i);
			nrc++;
		}
	}
	printf("%d",nrc);	
	return 0;	
}