Cod sursa(job #2889409)

Utilizator BalutaBaluta Iustinian-Lucian Baluta Data 12 aprilie 2022 18:56:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NLIM 100005

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int conexe;
int N, M;
bool vizitat[NLIM];

vector <int> Muchii[NLIM];

void DFS(int s)
{
	vizitat[s] = true;
	for (unsigned int y = 0; y < Muchii[s].size(); y++)
	{
		int vecin = Muchii[s][y];
		if (!vizitat[vecin])
			DFS(vecin);
	}
}

void Citire()
{
	int i, j, x, y;
	fin >> N >> M;
	for (i = 1; i <= M; i++)
	{
		fin >> x >> y;
		Muchii[x].push_back(y);
		Muchii[y].push_back(x);
	}
	for (i = 1; i <= N; i++)
	{
		if (!vizitat[i])
		{
			conexe++;
			DFS(i);
		}
	}
}

int main()
{
	Citire();
	fout << conexe;
	return 0;
}