Pagini recente » Cod sursa (job #243518) | Cod sursa (job #1581817) | Cod sursa (job #2669162) | Cod sursa (job #1135136) | Cod sursa (job #2907968)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m; // nr de noduri, respectiv de muchii
vector<vector<int>>vecini; // liste de adiacenta
vector<bool>vizitat; // marcarea varfurilor vizitate
int nrComponenteConexe;
void dfs(int nod){
vizitat[nod] = 1;
for(int i = 0; i < vecini[nod].size(); i++){
if(!vizitat[vecini[nod][i]]){
vizitat[vecini[nod][i]] = 1;
dfs(vizitat[vecini[nod][i]]);
}
}
}
int main(){
f >> n >> m;
vecini.resize(n + 1);
vizitat.resize(n + 1, 0);
for(int i = 0; i < m; i++){
int u, v;
f >> u >> v;
vecini[u].push_back(v);
vecini[v].push_back(u);
}
for(int i = 1; i <= n; i++)
if(!vizitat[i]){
nrComponenteConexe++;
dfs(i);
}
g << nrComponenteConexe;
return 0;
}