Cod sursa(job #804815)

Utilizator cremarencodianaCremarenco Diana cremarencodiana Data 30 octombrie 2012 15:23:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
# include <stdio.h>
# include <string.h>

using namespace std;
struct point {int inf; point *leg;}; 
point *p1, *ultim, *l[100010];
int n,x,y,s,nod,i,p,u,m;
bool viz[100010];

void dfs(int x)
{ 
	viz[x]=true;
	while (l[x])
	    if (viz[l[x]->inf]==false)
		{
			dfs(l[x]->inf);
			l[x]=l[x]->leg;
		}
		else l[x]=l[x]->leg;
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	memset(l,NULL,sizeof(l));
	scanf("%d %d\n",&n,&m);
	for (i=1; i<=m; i++)
	{
		p1 = new point;
		scanf("%d %d\n",&x,&y);
		p1->inf=y;
		p1->leg=l[x];
		l[x]=p1;
		ultim = new point;
		ultim->inf=x;
		ultim->leg=l[y];
		l[y]=ultim;
	}
	int n1=0;
	for (i=1; i<=n; i++)
	{
		if (viz[i]==false)
		{
		n1++;
		dfs(i);
		}
	}
	printf("%d\n",n1);
	return 0;
}