Pagini recente » Cod sursa (job #2711149) | Cod sursa (job #1430583) | Cod sursa (job #2091448) | Cod sursa (job #2617917) | Cod sursa (job #1611718)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void explore_component(const int x, const vector<vector<int>>& vec, vector<bool>& e_viz){
stack<int, vector<int>> st;
st.push(x);
e_viz[x] = true;
while(!st.empty()){
const int cur = st.top();
st.pop();
for(int i = 0; i < vec[cur].size(); ++i){
const int next = vec[cur][i];
if(!e_viz[next]){
e_viz[next] = true;
st.push(next);
}
}
}
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m;
f >> n >> m;
vector<vector<int> > vec(n);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
--a, --b;
vec[a].push_back(b);
vec[b].push_back(a);
}
vector<bool> e_viz(n, false);
int rez = 0;
for(int i = 0; i < n; ++i){
if(!e_viz[i]){
++rez;
explore_component(i, vec, e_viz);
}
}
g << rez << '\n';
return 0;
}