Pagini recente » Cod sursa (job #2216841) | Cod sursa (job #169678) | Cod sursa (job #3157382) | Cod sursa (job #1542576) | Cod sursa (job #1248459)
#include <fstream>
#include <vector>
using namespace std;
void dfs(
const size_t v,
vector<size_t>& visited,
const vector<vector<size_t>>& G) {
visited[v] = 1;
for (int u : G[v]) if (!visited[u]) {
dfs(u, visited, G);
}
}
int connected_components(const vector<vector<size_t>>& G) {
vector<size_t> visited(G.size(), 0);
int n = 0;
for (size_t v = 0; v < G.size(); ++v) if (!visited[v]) {
++n;
dfs(v, visited, G);
}
return n;
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m;
fin >> n >> m;
vector<vector<size_t>> G(n);
for (; m; --m) {
int u, v;
fin >> u >> v;
G[u-1].push_back(v-1);
G[v-1].push_back(u-1);
}
fout << connected_components(G) << endl;
return 0;
}