Pagini recente » Cod sursa (job #2468123) | Cod sursa (job #41958) | Cod sursa (job #2317669) | Cod sursa (job #470951) | Cod sursa (job #1431035)
#include<iostream>
#include<fstream>
#include<vector>
#define NR_NEIG 200
using namespace std;
struct Node {
int id;
Node* next;
};
void add_neigh(Node* &node, int id) {
Node* n = new Node();
n->id = id;
n->next = node;
node = n;
}
void dfs(Node* nodes[], bool visited[], int i) {
visited[i] = true;
Node* it = nodes[i];
while (it != NULL && !visited[it->id]) {
dfs(nodes, visited, it->id);
it = it->next;
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
int id1, id2;
Node* nodes[n + 1];
bool visited[n + 1];
for (int i = 1; i <= n; ++i) {
nodes[i] = NULL;
}
for (int i = 0; i < m; ++i) {
scanf("%d %d", &id1, &id2);
add_neigh(nodes[id1], id2);
add_neigh(nodes[id2], id1);
}
int ctc_no = 0;
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(nodes, visited, i);
ctc_no++;
}
}
printf("%d", ctc_no);
fclose(stdin);
fclose(stdout);
return 0;
}