Cod sursa(job #3369798)

Utilizator AlphxByteStefan Alexandru AlphxByte Data 22 octombrie 2026 10:24:21
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>

const std::string fileName = "dfs";
const int N = 1e5 + 1;

std::ifstream fin(fileName + ".in");
std::ofstream fout(fileName + ".out");

std::vector<int> graph[N];
std::vector<bool> visited(false);

void DFS(int node)
{
	visited[node] = true;

	for (const auto& neighbour : graph[node])
	{
		if (!visited[neighbour])
		{
			DFS(neighbour);
		}
	}
}

int main()
{
	int n, m;
	fin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int x, y;
		fin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	visited = std::vector<bool>(n + 1, false);
	
	int nrc = 0;
	for (int i = 0; i < n; ++i)
	{
		if (!visited[i])
		{
			++nrc;
			DFS(i);
		}
	}

	fout << nrc;

	return 0;
}