Cod sursa(job #248952)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 27 ianuarie 2009 09:49:33
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream.h>

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

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

void dfs(int x)
{       int i;
	viz[x]=kappa;
	sol[k++]=x;
        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;
}