Pagini recente » Cod sursa (job #2736003) | Cod sursa (job #165593) | Cod sursa (job #629246) | Cod sursa (job #2667895) | Cod sursa (job #3250889)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<vector<int>> adj; // Liste de adiacenta
vector<bool> visited; // Vector de vizitare
int N, M; // N = numarul de noduri, M = numarul de muchii
void dfs(int node)
{
visited[node] = true;
// Parcurgem vecinii nodului curent
for (int neighbor : adj[node])
{
if (!visited[neighbor])
{
dfs(neighbor);
}
}
}
int count_components()
{
int components = 0;
// Parcurgem fiecare nod
for (int i = 1; i <= N; i++)
{
if (!visited[i])
{
// Am gasit un nod nevizitat, deci o noua componenta conexa
components++;
dfs(i);
}
}
return components;
}
int main()
{
// Citim N si M
fin >> N >> M;
// Initializam listele de adiacenta si vectorul de vizitare
adj.resize(N + 1);
visited.resize(N + 1, false);
// Citim muchiile si construim listele de adiacenta
for (int i = 0; i < M; i++)
{
int x, y;
fin >> x >> y;
// Graful este neorientat, adaugam muchia in ambele directii
adj[x].push_back(y);
adj[y].push_back(x);
}
// Calculam si afisam numarul de componente conexe
fout << count_components();
fin.close();
fout.close();
return 0;
}