Cod sursa(job #146757)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 2 martie 2008 04:38:54
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
struct nod{long info;nod *next;};
nod *lv[100001];
long viz[100001],sol,i,x,y,n,m;
void pune(long a,long b);
void dfs(long a);
int main()
{   FILE *f=fopen("dfs.in","r"),
	 *g=fopen("dfs.out","w");
    fscanf(f,"%ld%ld",&n,&m);
    for(i=1;i<=m;i++) {fscanf(f,"%ld%ld",&x,&y);pune(x,y);pune(y,x);}
    for(i=1;i<=n;i++)
    if(!viz[i]){ sol++;viz[i]=1;dfs(i);}
    fprintf(g,"%ld",sol);
    fcloseall();
    return 0;
}
void pune(long a,long b)
{
	nod *paux;
	paux->info=b;
	if(!lv[a]){paux->next=0;lv[a]=paux;return;}
	paux->next=lv[a];lv[a]=paux;
}
void dfs(long a)
{
	nod *paux;
	paux=lv[a];
	while(paux)
	{ if(!viz[paux->info])
	  { viz[paux->info]=1;dfs(paux->info);}
	  paux=paux->next;
	}
}