Pagini recente » Cod sursa (job #3211106) | Cod sursa (job #2113674) | Cod sursa (job #2250803) | Cod sursa (job #2294808) | Cod sursa (job #2794245)
#include<stdio.h>
#include<stdlib.h>
typedef struct linked_list_node
{
struct linked_list_node *next;
int value;
} linked_list_node;
linked_list_node *Last_element[100005];
void add_element_to_linked_list(int which, int value)
{
linked_list_node *node=(linked_list_node *)malloc(sizeof(linked_list_node));
node->value=value;
node->next=Last_element[which];
Last_element[which]=node;
}
void add_edge(int x, int y)
{
add_element_to_linked_list(x,y);
add_element_to_linked_list(y,x);
}
int Viz[100005];
void dfs(int node)
{
Viz[node]=1;
for(linked_list_node *linked_list_element=Last_element[node]; linked_list_element!=NULL; linked_list_element=(linked_list_element->next))
{
int neighbour=linked_list_element->value;
if(!Viz[neighbour])
dfs(neighbour);
}
}
int main()
{
FILE *fi,*fo;
fopen_s(&fi,"dfs.in","r");
fopen_s(&fo,"dfs.out","w");
int n,m;
fscanf_s(fi,"%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int x,y;
fscanf_s(fi,"%d%d",&x,&y);
add_edge(x,y);
}
int rez=0;
for(int i=1; i<=n; i++)
{
if(!Viz[i])
{
rez++;
dfs(i);
}
}
fprintf_s(fo,"%d",rez);
fclose(fi);
fclose(fo);
return 0;
}