Cod sursa(job #585191)

Utilizator lily3Moldovan Liliana lily3 Data 28 aprilie 2011 12:48:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
using namespace std;
ofstream g("dfs.out");

int i,j,n,m,*a[100001],x,y,p,q,b[1000001],v[1000001];
void dfs(int x)
{
	//g<<x<<" ";
	v[x]=1;
	for(int i=1;i<=a[x][0];i++)
		if(!v[a[x][i]])
			dfs(a[x][i]);
}
int bfs(int x)
{
	int i,st=0,dr=0,c[101];
	v[x]=1;
	c[0]=x;
	//g<<x<<" ";
	while(st<=dr)
	{
		x=c[st++];
		for(i=1;i<=a[x][0];i++)
			if(!v[a[x][i]])
			{
				v[a[x][i]]=3-v[x];
				c[++dr]=a[x][i];
			//	g<<a[x][i]<<" ";
			}
			else
				if(v[a[x][0]]==v[x])
					return 0;
	}
	return 1;
}
void afis(int x)
{
	int i,d[101],r=0;
	if(v[x]==0)
		g<<-1;
	else
	{
		d[0]=x;
		while(v[d[r]]!=-1)
			d[++r]=v[d[r-1]];
		for(i=r;i>=0;i--)
			g<<d[i]<<" ";
	}
}
void bfs1(int x,int y)
{
	int i,st=0,dr=0,c[101];
	v[x]=-1;
	c[0]=x;
	while(st<=dr&&v[y]==0)
	{
		x=c[st++];
		for(i=1;i<=a[x][0];i++)
			if(!v[a[x][i]])
			{
				v[a[x][i]]=x;
				c[++dr]=a[x][i];
			}
	}
	afis(y);
}
int dfs1(int x,int p)
{
	int i;
	v[x]=1;
	for(i=1;i<=a[x][0];i++)
		if(!v[a[x][i]])
		{
			if(dfs1(a[x][i],x)==0)
				return 0;
		}
		else
			if(p!=a[x][i])
				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;
	}
	//bfs1(p,q);
	int ok=0;
	for(i=1;i<=n;i++)
		if(!v[i])
		{
			ok++;
			dfs(i);
		}
		g<<ok;
	return 0;
}