Cod sursa(job #878917)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 14 februarie 2013 20:37:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb

#include <cstdio>
#include <vector>

const int MAX_SIZE(100001);

int n, m, components;

std::vector<int> graph [MAX_SIZE];
bool mark [MAX_SIZE];

inline void read (void)
{
	std::freopen("dfs.in","r",stdin);
	std::scanf("%d %d",&n,&m);
	int x, y;
	for (int counter(0) ; counter < m ; ++counter)
	{
		std::scanf("%d %d",&x,&y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("dfs.out","w",stdout);
	std::printf("%d\n",components);
	std::fclose(stdout);
}

void DepthFirstSearch (int node)
{
	mark[node] = true;
	for (int j(0), size(graph[node].size()) ; j < size ; ++j)
		if (!mark[graph[node][j]])
			DepthFirstSearch(graph[node][j]);
}

int main (void)
{
	read();
	for (int node(1) ; node <= n ; ++node)
		if (!mark[node])
		{
			DepthFirstSearch(node);
			++components;
		}
	print();
	return 0;
}