Pagini recente » Cod sursa (job #1823092) | Cod sursa (job #2133848) | Cod sursa (job #1218765) | Cod sursa (job #1176303) | Cod sursa (job #1857128)
#include<stdio.h>
#include<stdlib.h>
#define MAX_N 100001
struct arc *graph[MAX_N];
int visited[MAX_N];
int N, M;
int connected;
struct arc {
int d;
struct arc *next;
};
void dfs(int pos) {
struct arc *p = graph[pos];
visited[pos] = 1;
while(p) {
if(!visited[p->d])
dfs(p->d);
p = p->next;
}
}
void add_node(int x, int y)
{
struct arc *node = calloc(sizeof(struct arc), 1);
node->d = y;
node->next = graph[x];
graph[x] = node;
}
int main(void)
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++) {
graph[i] = NULL;
}
for(int i = 0; i < M; i++) {
int x,y;
scanf("%d %d", &x, &y);
add_node(x, y);
add_node(y, x);
}
for(int i = 1; i <= N; i++) {
if(!visited[i]) {
connected++;
dfs(i);
}
}
printf("%d\n", connected);
}