Cod sursa(job #249340)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 28 ianuarie 2009 01:27:12
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream.h>

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int a[1005][1005],j,n,viz[1005],x,y,kappa,m,k=1;

void dfs(int x)
{       int i;
	viz[x]=kappa;
        for(i=1;i<=n;i++)
        	if(a[i][x]&&!viz[i])
                	dfs(i);
}

int main()
{       int i;
	fin>>n>>m;
	for(i=1;i<=m;i++)
        {	fin>>x>>y;
        	a[x][y]=a[y][x]=1;
        }
	for(i=1;i<=n;i++)
        {	if(!viz[i])
        	{	kappa++;
                	dfs(i);
	                /*for(j=1;j<k;j++)
        	        	fout<<sol[j]<<' ';
	                fout<<'\n';*/
                        k=1;
                }
        }
        fout<<kappa<<'\n';
        return 0;
}