Cod sursa(job #2271369)

Utilizator al3xionescuIonescu Alexandru al3xionescu Data 28 octombrie 2018 14:29:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
	
#define MAX 300001
	
int n,m,v[2][MAX],cont;
	
void add(int x,int y)
	
{
	
	if(!v[1][x])
	
	{
	
		v[1][x] = cont;
	
		v[0][cont] = y;
	
		v[1][cont] = 0;
	
	}
	
	else
	
	{
	
		v[1][v[0][x]] = cont;
	
		v[0][cont] = y;
	
		v[1][cont] = 0;		
	
	}
	
	v[0][x] = cont;
	
}
	
void df(int i)
	
{
	
	int var;
	
	while(v[1][i]>0)
	
	{
	
		var = v[1][i];
	
		v[1][i] = v[1][v[1][i]];
	
		
	
		if(!v[1][i])v[1][i] = -1;
	
		df(v[0][var]);
	
	}
	
}
	
int main()
	
{
	
	FILE*f = fopen("dfs.in","r");
	
	fscanf(f,"%d %d",&n,&m);
	
	int i,a,b;
	
	cont = n+1;
	
	for(i=1;i<=m;++i,++cont)
	
	{
	
		fscanf(f,"%d%d",&a,&b);
	
		add(a,b);
	
		++cont;
	
		add(b,a);
	
	}
	
	fclose(f);
	
	for(i = 1,cont = 0;i<=n;++i)
	
	{
	
		if(v[1][i]>=0)
	
		{
	
			++cont;
	
			df(i);
	
		}
	
	}
	
	FILE*g = fopen("dfs.out","w");
	
	fprintf(g,"%d\n",cont);
	
	fclose(g);
	
	return 0;
	
}