Pagini recente » Cod sursa (job #512645) | Cod sursa (job #3234075) | Cod sursa (job #3234053) | Cod sursa (job #518869) | Cod sursa (job #2859573)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int main()
{ int V, E;
fin >> V >> E;
vector<vector<int>> adjList(V + 1, vector<int>());
vector<int> vis(V + 1, false);
for(int i = 1; i <= E; ++i) {
int v1, v2;
fin >> v1 >> v2;
adjList[v1].push_back(v2);
adjList[v2].push_back(v1);
}
int connectedComponents = 0;
for(int i = 1; i <= V; ++i) {
if(vis[i] == false) {
++connectedComponents;
stack<int> recursionStack;
recursionStack.push(i);
while(!recursionStack.empty()) {
int crt = recursionStack.top();
recursionStack.pop();
for(auto ngb: adjList[crt]) {
if(vis[ngb] == false) {
vis[ngb] = true;
recursionStack.push(ngb);
}
}
}
}
}
fout << connectedComponents;
return 0;
}