Cod sursa(job #280564)

Utilizator nighthawkghenea alexandru madalin nighthawk Data 13 martie 2009 14:12:10
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream.h>

ifstream f("dfs.in");
ofstream g("dfs.out");

int a[100][100],viz[1000],n,contor;


void parcurgere( int x)
{int coada[1000]={0},cc=1,ci=1;
 viz[x]=1;
 contor++;
 while(cc>=ci)
	{for(int i=1;i<=n;i++)
		if(a[i][x]&&!viz[i])
			{cc++;
			coada[cc]=i;
	
			viz[i]=1;
			}
	ci++;
	x=coada[ci];
	}
}


int main()
{
 long x,y,m;
 int sw=1,i;
 f>>n;
 f>>m;
 for( i=0;i<m;i++)
	{f>>x;
	f>>y;
	a[x][y]=a[y][x]=1;}
 while(sw)
	{sw=0;
	for(i=1;i<=n;i++)
		{if(!viz[i])
			{parcurgere(i);
			sw=1;}
		}
	}
 g<<contor;
 g.close();
 return 0;
}