Pagini recente » Cod sursa (job #2515716) | Cod sursa (job #3187681) | Cod sursa (job #881827) | Borderou de evaluare (job #2021034) | Cod sursa (job #2033308)
#include <stdio.h>
#include <stdlib.h>
#define nMax 100001
FILE *in, *out;
int viz[nMax];
typedef struct node {
int data;
struct node* next;
} node;
node* head[nMax];
node* create(int data, node* next)
{
node* new_node = (node*)malloc(sizeof(node));
if(new_node == NULL) {
fprintf(out, "Error when creating a new node\n");
return NULL;
}
new_node->data = data;
new_node->next = next;
return new_node;
}
node* insertFront(int data, node* head)
{
node* new_node = create(data, head);
head = new_node;
return head;
}
void dfs(int current, int father)
{
viz[current] = 1;
node* cursor = head[current];
while(cursor != NULL) {
int son = cursor->data;
cursor = cursor->next;
if(son == father) {
continue;
}
if(viz[son] == 0) {
dfs(son, current);
}
}
}
int main()
{
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");
int n, m, a, b;
fscanf(in, "%d%d", &n, &m);
int i;
for(i=0; i<nMax; i++) {
head[i] = NULL;
}
for(i=1; i<=m; i++) {
fscanf(in, "%d%d", &a, &b);
head[b] = insertFront(a, head[b]);
head[a] = insertFront(b, head[a]);
}
int conex_components = 0;
for(i=1; i<=n; i++) {
if(viz[i] == 0) {
dfs(i, 0);
conex_components++;
}
}
fprintf(out, "%d", conex_components);
return 0;
}