Pagini recente » Cod sursa (job #1846280) | Cod sursa (job #1912965) | Cod sursa (job #1954588) | Cod sursa (job #424267) | Cod sursa (job #253366)
Cod sursa(job #253366)
#include <stdio.h>
#include <stdlib.h>
#define in "dfs.in"
#define out "dfs.out"
#define MAX 100001
struct edge
{
long node;
struct edge *next;
};
struct node
{
int visited;
struct edge *node;
};
struct node graph[MAX];
long n, nr = 0;
//add a new edge to graph
void add_edge(long x, long y)
{
//create a new node
struct edge *new_edge;
if ((new_edge = (struct edge *)malloc(sizeof(struct edge))) == NULL)
{
printf("Not enoug memory\n");
exit(-1);
}
new_edge->node = y;
new_edge->next = graph[x].node;
//add a new tail edge
graph[x].node = new_edge;
}
void read_file()
{
FILE *fin;
long int x, y, m, i;
if ((fin = fopen(in, "r")) == NULL)
{
printf("Eroare \n");
exit(-1);
}
//read the two nodes
fscanf(fin, "%ld%ld", &n, &m);
for (i = 1; i <=n ; i++)
{
graph[i].visited = 0;
graph[i].node = NULL;
}
for (i = 0; i < m; i++)
{
fscanf(fin, "%ld%ld", &x, &y);
//add a new node in graph
add_edge(x, y);
add_edge(y, x);
}
fclose(fin);
}
void dfs(long node)
{
struct edge *t;
graph[node].visited = 1;
//add the unvisited nodes to queue
for (t = graph[node].node; t != NULL; t = t->next)
{
if (graph[t->node].visited == 0)
{
dfs(t->node);
}
}
}
void solve()
{
long i;
for (i = 1 ; i <= n; i++)
if (graph[i].visited == 0)
{
dfs(i);
nr++;
}
}
void print_file()
{
FILE *fout;
fout = fopen(out, "w");
fprintf(fout, "%ld", nr);
fclose(fout);
}
int main()
{
read_file();
solve();
print_file();
return 0;
}