Pagini recente » Cod sursa (job #145262) | Cod sursa (job #2907526) | Cod sursa (job #1938996) | Cod sursa (job #2549019) | Cod sursa (job #2846151)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int start, vector<bool> &seen, const vector<vector<int>> &adj)
{
stack<pair<int,int>> st;
st.push({start,0});
seen[start] = true;
while (!st.empty()) {
pair<int,int> &t = st.top();
int nod = it.first;
int i = t.second;
if (i < adj[nod].size()) {
int v = adj[nod][i];
t.second = i + 1;
if (!seen[v]) {
seen[v] = true;
st.push({v,0});
}
}
else {
st.pop();
}
}
}
int main(){
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int n, m;
fin >> n >> m;
vector<vector<int>> adj(n+1);
for (int i = 0; i < m; ++i) {
int a, b;
fin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<bool> seen(n+1, false);
int nrComp = 0;
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
++nrComp;
dfs(i, seen, adj);
}
}
fout << nrComp << endl;
}