Pagini recente » Cod sursa (job #2037473) | Cod sursa (job #3123326) | Cod sursa (job #678952) | Cod sursa (job #3178489) | Cod sursa (job #3293991)
#include <bits/stdc++.h>
using namespace std;
ifstream f("dfs.in");
ofstream gg("dfs.out");
// g[i] = lista de vecini a nodului i
vector<int> g[100005];
// viz[i] = true daca nodul i a fost deja vizitat
bool viz[100005];
int n, m; // n = numar de noduri, m = numar de muchii
// Functie DFS care viziteaza toate nodurile conectate cu 'nod'
void dfs(int nod)
{
viz[nod] = true; // Marcam nodul ca vizitat
// Parcurgem toti vecinii nodului curent
for (auto vec : g[nod])
if (!viz[vec])
dfs(vec);
}
int main()
{
f >> n >> m;
// Citim cele m muchii si construim graful
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
g[x].push_back(y); // Adaugam y in lista de vecini a lui x
g[y].push_back(x); // Adaugam x in lista de vecini a lui y
}
int cnx = 0; // Numarul de componente conexe
// Parcurgem toate nodurile
for (int i = 1; i <= n; i++)
if (!viz[i]) // Daca nodul nu a fost vizitat
{
dfs(i); // Pornim un DFS din acel nod
cnx++; // Am gasit o noua componenta conexa
}
gg << cnx; // Afisam numarul total de componente conexe
return 0;
}