Pagini recente » Cod sursa (job #2491493) | Cod sursa (job #1809323) | Cod sursa (job #643100) | Cod sursa (job #3292367) | Cod sursa (job #1977638)
#include <bits/stdc++.h>
using namespace std;
struct node {
int n;
node *next;
};
void add_node(node **dest, int n)
{
node *new_node = new node;
new_node->n = n;
new_node->next = *dest;
*dest = new_node;
}
void DFS(int i, vector<bool> &visited, vector<node*> nodes)
{
visited[i] = 1;
for (node *p = nodes[i]; p != nullptr; p = p->next) {
if (!visited[p->n]) {
DFS(p->n, visited, nodes);
}
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<node*> nodes(n);
for (int i = 0; i < n; i++) {
nodes[i] = new node;
nodes[i]->next = nullptr;
}
for (int i = 0, x, y; i < m; i++) {
cin >> x >> y;
add_node(&nodes[x], y);
add_node(&nodes[y], x);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) visited[i] = 0;
int solution = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
solution++;
DFS(i, visited, nodes);
}
}
cout << solution << "\n";
return 0;
}