Pagini recente » Cod sursa (job #1332002) | Cod sursa (job #1773712) | Cod sursa (job #1220185) | Cod sursa (job #2306048) | Cod sursa (job #2746302)
///#539 in pbinfo
///the graph is UNoriented
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> ///pentru a putea folosi boool
FILE *f,*g;
bool viz[101];
typedef struct sll
{
int value;
struct sll *next;
}sll;
sll* v[101];
void dfs(int start, int n, sll* v[])
{
viz[start]=1;
int i;
sll* ve=v[start];
while(ve != NULL)
{
if(!viz[ve->value])
dfs(ve->value,n,v);
ve=ve->next;
}
}
sll* create( int n2)
{
sll* p;
p=(sll* )calloc(1,sizeof(sll));
if(p)
{
p->value=n2;
p->next=NULL;
}
else
{
printf("Nu s-a putut aloca memoria!");
exit(2);
}
}
void insert(sll* v[], int n1, int n2)
{
sll* p;
p=create(n2);
if(v[n1] == NULL)///nu am niciun element
v[n1]=p;
else///am cel putin un element
{///trebuie inserati vecinii in ordine crescatoare
if(v[n1]->value > n2)
{
p->next=v[n1];
v[n1]=p;///se va modifica v[n1]
}
else
{
sll* p1=v[n1];
sll* p2=v[n1]->next;
while(p2 != NULL)
{
if(p1->value <= n2 && n2 <= p2->value)
{
p->next=p2;
p1->next=p;
break;
}
p1=p2;
p2=p2->next;
}
if(p2==NULL)///se va insera la final
p1->next=p;
}
}
}
int main()
{
f=fopen("dfs.in","r");
if(!f)
{
printf("The input file can not be opend!");
exit(1);
}
g=fopen("dfs.out","w");
if(!g)
{
printf("The output file can not be opened!");
exit(1);
}
int n,m,x,n1,n2;
///int matric[100][100]={0};
fscanf(f,"%d %d",&n,&m);
int i;
for(i=0;i<=n;++i) v[i]=NULL;///!!!
for(i=1;i<=m;++i)
{
fscanf(f,"%d %d",&n1,&n2);
insert(v,n1,n2);
insert(v,n2,n1);
}
int nr=0;
for(i=1;i<=n;++i)
if(!viz[i])
{
++nr;
dfs(i,n,v);
}
fprintf(g,"%d",nr);
fclose(f);
fclose(g);
return 0;
}