Pagini recente » Cod sursa (job #2990371) | Cod sursa (job #2164063) | Cod sursa (job #550258) | Cod sursa (job #1261094) | Cod sursa (job #2302626)
#include <stdio.h>
#include <stdlib.h>
struct nod {
int val;
struct nod *next;
};
void baga(struct nod **q, int val) {
if (q == NULL) {
(*q) = malloc(sizeof(struct nod));
(*q) -> next = NULL;
(*q) -> val = val;
return;
}
struct nod *p = malloc(sizeof(struct nod));
p -> next = *q;
p -> val = val;
*q = p;
}
void dfs(int p, int *viz, struct nod **q) {
viz[p] = 1;
for (struct nod *v = q[p]; v != NULL; v = v -> next)
if (!viz[v -> val])
dfs(v -> val, viz, q);
}
int main() {
FILE *in = fopen("dfs.in", "r");
FILE *out = fopen("dfs.out", "w");
int n, m;
fscanf(in, "%d %d", &n, &m);
int *viz = calloc(n, sizeof(int));
struct nod **q = calloc(n, sizeof(struct nod *));
for (int i = 0; i < m; i++) {
int x, y;
fscanf(in, "%d %d", &x, &y);
baga(&q[x - 1], y - 1);
baga(&q[y - 1], x - 1);
}
int nr = 0;
for (int i = 0; i < n; i++)
if (viz[i] == 0) {
dfs(i, viz, q);
nr++;
}
fprintf(out, "%d", nr);
return 0;
}