Cod sursa(job #1044632)

Utilizator rvnzphrvnzph rvnzph Data 30 noiembrie 2013 10:03:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

vector <int> g[100001];
int use[100001];

void dfs(int at)
{
	use[at]=1;

	for(vector<int>::iterator it=g[at].begin();it!=g[at].end();++it)
		if(!use[*it]) dfs(*it);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	int M,N,x,y;

	scanf("%d%d",&N,&M);
	while(M--)
	{
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	memset(use,0,sizeof(use));
	int cnt=0;

	for(int i=1;i<=N;++i)
		if(!use[i])
			dfs(i), ++cnt;

	printf("%d\n",cnt);

	return 0;
}