Pagini recente » Cod sursa (job #1957105) | Cod sursa (job #2265200)
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100001
#define MAX_EDGES 200001
struct edge_t {
int node;
int next;
} edges[MAX_EDGES];
int graph[MAX_NODES], edge_it = 1;
bool vis[MAX_NODES];
int add_edge(int x, int y)
{
edges[edge_it] = (struct edge_t){y, graph[x]};
graph[x] = edge_it++;
}
void dfs(int node)
{
struct edge_t edge = edges[graph[node]];
vis[node] = true;
while (edge.node) {
if (!vis[edge.node])
dfs(edge.node);
edge = edges[edge.next];
}
}
int main()
{
freopen("dfs.in", "r", stdin);
// freopen("dfs.out", "w", stdout);
int n, m, x, y, sol = 0;
scanf("%d %d", &n, &m);
while (m--) {
scanf("%d %d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i);
sol++;
}
}
printf("%d", sol);
return 0;
}