Pagini recente » Cod sursa (job #1616503) | Cod sursa (job #760542) | Cod sursa (job #227920) | Cod sursa (job #759725) | Cod sursa (job #2089062)
#include <stdlib.h>
#include <stdio.h>
struct node {
int data;
struct node *next;
};
int list_add_first(struct node **head, int val)
{
struct node *tmp = malloc(sizeof(struct node));
tmp->data = val;
tmp->next = *head;
*head = tmp;
return 0;
}
void dfs(struct node **graph, int s, int* marked)
{
if (graph[s] == NULL)
return;
for (struct node *p = graph[s]; p!= NULL; p = p->next){
if(!marked[p->data]) {
marked[p->data] = 1;
dfs(graph, p->data, marked);
}
}
}
int main()
{
FILE *infile, *outfile;
struct node **graph;
int n, m;
int *marked;
int count = 0;
infile = fopen("dfs.in", "r");
outfile = fopen("dfs.out", "w");
fscanf(infile, "%d %d", &n, &m);
marked = malloc ((n+1) * sizeof(int));
graph = malloc((n+1) * sizeof(struct node*));
for (int i = 0; i <= n ; i++) {
graph[i] = NULL;
marked[i] = 0;
}
for (int i = 0; i < m ;i++) {
int x, y;
fscanf(infile, "%d %d", &x, &y);
list_add_first(&graph[x], y);
list_add_first(&graph[y], x);
}
for (int i = 1; i <= n; i++) {
if(marked[i] == 0) {
count++;
dfs(graph, i, marked);
}
}
fprintf(outfile, "%d", count);
}