Pagini recente » Cod sursa (job #2274271) | Cod sursa (job #1582652) | Cod sursa (job #93398) | Cod sursa (job #510944) | Cod sursa (job #773391)
Cod sursa(job #773391)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector <int> vecin[nmax];
bool vizitat[nmax];
int top;
void dfs(int curent) {
vizitat[curent] = true; //nodul curent marcat ca vizitat
for(int i = 0; i < int(vecin[curent].size()); i++) { //ii iau toti vecinii
if(!vizitat[ vecin[curent][i] ]) dfs(vecin[curent][i]); //pentru cei nevizitati fac un dfs
}
}
int main() {
int n, m, i, a, b, rez=0;
f>>n>>m;
for(i=1; i<=m; i++) {
f>>a>>b;
vecin[a].push_back(b); //graf neorientat
vecin[b].push_back(a); //graf neorientat
}
for(i=1; i<=n; i++) {
if(!vizitat[i]) { //incep cu dfs(1), care imi marcheaza ca fiind vizitate toate nodurile
rez++; //primei componente conexe. reiau nodurile nevizitate (componente noi)
dfs(i); //si fac aceeasi chestie, numarand componentele
}
}
g<<rez<<"\n";
f.close();
g.close();
return 0;
}