Pagini recente » Cod sursa (job #1106025) | Cod sursa (job #2677481) | Cod sursa (job #1025658) | Cod sursa (job #992138) | Cod sursa (job #1523384)
#include <stdio.h>
#include <stdlib.h>
typedef struct nod
{
int nr;
struct nod *urm;
}NOD;
int n,m,nr_comp;
char marc[100001];
NOD *graf[100001];
void add(int x,int y)
{
NOD *p=malloc(sizeof(NOD));
p->nr=y;
p->urm=graf[x];
graf[x]=p;
}
void dfs(int v)
{
NOD *p;
for (p=graf[v];p!=NULL;p=p->urm)
if(marc[p->nr]==0)
{
marc[p->nr]=1;
dfs(p->nr);
}
}
int main()
{
int i,x,y;
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
fscanf(f,"%d%d",&n,&m);
for (i=0;i<m;i++)
{
fscanf(f,"%d%d",&x,&y);
add(x,y);
add(y,x);
}
for (i=1;i<=n;i++)
if (marc[i]==0)
{
marc[i]=1;
nr_comp++;
dfs(i);
}
fprintf(g,"%d\n",nr_comp);
fclose(f);
fclose(g);
return 0;
}