Pagini recente » Cod sursa (job #1105257) | Cod sursa (job #448073) | Cod sursa (job #211893) | Cod sursa (job #1455310) | Cod sursa (job #2219422)
#include <stdio.h>
#include <stdlib.h>
struct list {
int node;
struct list *next;
}* list[100000];
char visited[100000];
void add_neighbour(int vertex, int neighbour) {
struct list *aux;
aux = malloc(sizeof(list));
aux->next = list[vertex];
aux->node = neighbour;
list[vertex] = aux;
}
void dfs(int vertex) {
struct list *aux;
aux = list[vertex];
visited[vertex] = 1;
for (aux = list[vertex]; aux != NULL; aux = aux->next)
if (!visited[aux->node])
dfs(aux->node);
}
void freemem(struct list *list) {
struct list *aux;
while (list != NULL) {
aux = list;
list = list->next;
free(aux);
}
}
int main()
{
int conexe = 0;
int n, m;
int k, j;
int i;
FILE *in;
FILE *out;
in = fopen("dfs.in", "r");
fscanf(in, "%d %d", &n, &m);
for (i = 0; i < m; i++) {
fscanf(in, "%d %d", &k, &j);
add_neighbour(k, j);
add_neighbour(j, k);
}
fclose(in);
for (i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
conexe++;
}
}
out = fopen("dfs.out", "w");
fprintf(out, "%d", conexe);
fclose(out);
for (i = 1; i <= n; i++) {
freemem(list[i]);
}
return 0;
}