Pagini recente » Cod sursa (job #605504) | Cod sursa (job #1104545) | Cod sursa (job #2346025) | Cod sursa (job #1725642) | Cod sursa (job #2219420)
#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;
int value;
aux = list[vertex];
visited[vertex] = 1;
while (aux != NULL) {
value = aux->node;
if (!visited[value]) {
dfs(value);
}
aux = aux->next;
}
}
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;
}