Pagini recente » Rating Laura Chiriac (laura.chiriac) | Cod sursa (job #2704216) | Cod sursa (job #1216770) | Cod sursa (job #2577670) | Cod sursa (job #2749875)
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> adj[NMAX];
void dfs(int node, vector<int>& visited) {
visited[node] = 1;
for (auto child : adj[node])
if (!visited[child])
dfs(child, visited);
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int node_in, node_out;
fin >> node_in >> node_out;
adj[node_in].push_back(node_out);
adj[node_out].push_back(node_in);
}
int nr_componente = 0;
vector<int> visited(n + 1, 0);
// find the starting position
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) {
dfs(i, visited);
nr_componente++;
}
}
fout << nr_componente;
}