Pagini recente » Cod sursa (job #1953173) | Istoria paginii runda/haicatrebuiesatrebuiasca/clasament | Cod sursa (job #1518017) | Cod sursa (job #2546655) | Cod sursa (job #1705662)
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_NODES 100000
std::vector<int> adj_list[MAX_NODES + 1];
void explore(int curr_node, int visited[]) {
visited[curr_node] = 1;
for (auto &adj_node : adj_list[curr_node]) {
if (!visited[adj_node]) {
explore(adj_node, visited);
}
}
}
int dfs(int num_nodes, int visited[]) {
int cc = 0;
for (int i = 1; i <= num_nodes; i++) {
visited[i] = 0;
}
for (int i = 1; i <= num_nodes; i++) {
if (!visited[i]) {
cc++;
explore(i, visited);
}
}
return cc;
}
int main(void) {
FILE * fin = fopen("dfs.in", "r");
FILE * fout = fopen("dfs.out", "w");
int n, m, s, x, y;
fscanf(fin, "%d%d", &n, &m);
int visited[n + 1];
for (int i = 0; i < m; i++) {
fscanf(fin, "%d%d", &x, &y);
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
fprintf(fout, "%d", dfs(n, visited));
fclose(fin);
fclose(fout);
}