Cod sursa(job #745359)

Utilizator fhandreiAndrei Hareza fhandrei Data 11 mai 2012 12:26:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
//Include
#include <fstream>
#include <vector>
using namespace std;

//Definitii
#define pb push_back

//Constante
const int MAX_SIZE = (int)1e5+1;

//Functii
void dfs(int node);

//Variabile
ifstream in("dfs.in");
ofstream out("dfs.out");

int nodes, edges;
int answer;
int visited[MAX_SIZE];

vector<int> graph[MAX_SIZE];

//Main
int main()
{
	in >> nodes >> edges;
	int cFrom, cTo;
	while(edges--)
	{
		in >> cFrom >> cTo;
		graph[cFrom].pb(cTo);
		graph[cTo].pb(cFrom);
	}
	
	for(int i=1 ; i<=nodes ; ++i)
		if(!visited[i])
			dfs(i), ++answer;
	
	out << answer;
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node)
{
	visited[node] = true;
	
	vector<int>::iterator it=graph[node].begin(), end=graph[node].end();
	for(; it!=end ; ++it)
		if(!visited[*it])
			dfs(*it);
}