Cod sursa(job #640733)

Utilizator KandaonMihaescu Tiberiu Kandaon Data 26 noiembrie 2011 13:47:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
struct nod{
	int info;
	nod *adr;
};
nod *v[100001];
int viz[100001];

void leg(int a, int b)
{nod *temp=new nod;
temp->info=b;
temp->adr=v[a];
v[a]=temp;
}

void parc(int k)
{viz[k]=1;
nod *temp;
temp=v[k];
while(temp!=NULL)
	{if(viz[temp->info]!=1)
		parc(temp->info);
	temp=temp->adr;
	}

}

int main()
{freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);

int n,m,cate=0,i,a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
	{scanf("%d%d",&a,&b);
	leg(a,b);
	leg(b,a);
	}
for(i=1;i<=n;i++)
	if(viz[i]==0)
		{parc(i);
		cate++;
		}
printf("%d",cate);
return 0;
}