Cod sursa(job #393812)

Utilizator preda_alexandruPreda Alexandru preda_alexandru Data 9 februarie 2010 23:00:31
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.44 kb
#include<iostream.h>
#include<fstream.h>

int a[1001][1001],sel[1001],n;

void dfs(int s,int nrc)
{
int i;
sel[s]=nrc;
for(i=1;i<=n;i++)if(!sel[i] && a[s][i])dfs(i,nrc);
}

int main()
{
int i,c=0,m,x,y;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin>>n>>m;
for(i=1;i<=m;i++){
				 fin>>x>>y;
				 a[x][y]=1;
				 a[y][x]=1;
				 }
for(i=1;i<=n;i++)if(!sel[i]){
							c++;
							dfs(i,c);
							}
fout<<c;
return 0;
}