Cod sursa(job #1529506)

Utilizator ionutmodoModoranu Ionut-Vlad ionutmodo Data 20 noiembrie 2015 23:03:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
/*
	Parcurgere DFS - componente conexe
	http://www.infoarena.ro/problema/dfs
*/

#define MAX 100001
#define INPUT "dfs.in"
#define OUTPUT "dfs.out"

#include <fstream>
#include <vector>
using namespace std;

int N, M, comp;
bool used[MAX];
vector<int> L[MAX];

void read(void)
{
	int i, x, y;
	ifstream fin(INPUT);
	fin >> N >> M;
	for (i = 0; i < M; ++i)
	{
		fin >> x >> y;
		L[x].push_back(y);
		L[y].push_back(x);
	}
	fin.close();
}

void DFS(int node)
{
	used[node] = true;
	for (int i = 0; i < L[node].size(); ++i)
	{
		int other = L[node][i];
		if (!used[other])
		{
			DFS(other);
		}
	}
}

void solve(void)
{
	for (int i = 1; i <= N; ++i)
	{
		if (!used[i])
		{
			++comp;
			DFS(i);
		}
	}
}

void write(void)
{
	ofstream fout(OUTPUT);
	fout << comp << "\n";
	fout.close();
}

int main()
{
	read();
	solve();
	write();
	return 0;
}