Pagini recente » Cod sursa (job #1684586) | Cod sursa (job #156123) | Cod sursa (job #2248244) | Cod sursa (job #1673992) | Cod sursa (job #1426183)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void dfs(const vector<vector<int> >& adiacente, const int s, vector<bool>& gasit){
gasit[s] = true;
stack<int> de_viz;
de_viz.push(s);
int cur;
while(!de_viz.empty()){
cur = de_viz.top();
de_viz.pop();
for(auto next : adiacente[cur]){
if(!gasit[next]){
de_viz.push(next);
gasit[next] = true; } } } }
int main(){
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m;
f >> n >> m;
vector<vector<int> > adiacente(n);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
--a, --b;
adiacente[a].push_back(b);
adiacente[b].push_back(a); }
vector<bool> gasit(n, false);
int rez = 0;
for(int i = 0; i < n; ++i){
if(!gasit[i]){
++rez;
dfs(adiacente, i, gasit); } }
g << rez;
return 0; }