Cod sursa(job #1193799)

Utilizator stanescu.raduRadu Stanescu stanescu.radu Data 1 iunie 2014 20:24:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <vector>
#include <fstream>
#define PB push_back

using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

int n, m, sol;
bool viz[100005] = {false};
vector <int> v[100005];

void read ()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		f >> x >> y;
		v[x].PB(y);
		v[y].PB(x);
	}
}

void DFS (int x)
{
	viz[x] = true;
	
	for (int i = 0; i < v[x].size(); i++)
		if (!viz[v[x][i]]) 
			DFS(v[x][i]);
	v[x].clear();
	return ;
}

int main ()
{
	read ();
	for (int i = 1; i <= n ; i++)
	{
		if (viz[i] == 0)
		{
			DFS(i);
			sol ++;
		}
	}
	g << sol;
	f.close();
	
	return 0;
}