Cod sursa(job #3196249)

Utilizator PieleVoinescu David Piele Data 23 ianuarie 2024 12:14:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

const int NMAX = 100001;
const int INF = 1e9;

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

int N, M, Start;
std::vector<int>G[NMAX];
int Viz[NMAX];
int Dist[NMAX];

void Citire()
{
	fin >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void Dfs(int nod)
{
	Viz[nod] = 1;
	for (auto& x : G[nod])
	{
		if (!Viz[x])
		{
			Dfs(x);
		}
	}
}


void Afisare()
{
	int nr_componente = 0;
	for (int i = 1; i <= N; ++i)
	{
		if (!Viz[i])
		{
			Dfs(i);
			nr_componente++;
		}
	}

	fout << nr_componente;
}

int main()
{
	Citire();
	//Bfs();
	Afisare();
}