Pagini recente » Cod sursa (job #2761164) | Cod sursa (job #2434288) | Cod sursa (job #1007716) | Cod sursa (job #465147) | Cod sursa (job #2746319)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
FILE *f,*g;
bool viz[100001];
typedef struct sll
{
int value;
struct sll *next;
}sll;
sll* v[100001];
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;
}
}
void insert(sll* v[], int n1, int n2)
{
sll* p;
p=create(n2);
if(v[n1] == NULL)
v[n1]=p;
else
{
if(v[n1]->value > n2)
{
p->next=v[n1];
v[n1]=p;
}
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)
p1->next=p;
}
}
}
int main()
{
f=fopen("dfs.in","r");
g=fopen("dfs.out","w");
int n,m,x,n1,n2;
fscanf(f,"%d %d",&n,&m);
int i;
for(i=1;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\n",nr);
fclose(f);
fclose(g);
return 0;
}