Cod sursa(job #585186)

Utilizator valentina506Moraru Valentina valentina506 Data 28 aprilie 2011 12:43:11
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
using namespace std;
ofstream g("dfs.out");
int n,m,i,j,*a[101],x,y,p,q,c[1001],ok;
int viz[101];
void df(int x)
{
	int i;
	//g<<x<<" ";
	viz[x]=1;
	for(i=1;i<=a[x][0];i++)
		if(!viz[a[x][i]])
			df(a[x][i]);
}
int bf(int x)
{
	int i,prim,ultim;
//	g<<x<<" ";
	viz[x]=1;
	c[0]=x;                               
	prim=ultim=0;
	while(prim<=ultim)
	{
		x=c[prim++];
		for(i=1;i<=a[x][0];i++)
			if(!viz[a[x][i]])
			{
				//g<<a[x][i]<<" ";
			viz[a[x][i]]=3-viz[x];
			c[++ultim]=a[x][i];
			}
			else
				if(viz[a[x][i]]==viz[x])
					return 0;
				
	}
	return 1;
	
}
int main()
{
	ifstream f("dfs.in");
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		a[i]=(int *) realloc (a[i],sizeof(int));
	    a[i][0]=0;
	}
	while(f>>x>>y)
	{
		a[x][0]++;
		a[x]=(int *) realloc (a[x],(a[x][0]+1)*sizeof(int));
		a[x][a[x][0]]=y;
		a[y][0]++;
		a[y]=(int *) realloc (a[y],(a[y][0]+1)*sizeof(int));
		a[y][a[y][0]]=x;
	}
	ok=0;
	for(i=1;i<=n;i++)
		if(!viz[i])
		{
			df(i);
			ok++;
		}
		g<<ok;
	return 0;
}