Cod sursa(job #156195)

Utilizator rethosPaicu Alexandru rethos Data 12 martie 2008 13:30:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream.h>
#define NM 100001
struct lista{int nod;lista *urm;} *g[NM];
long nr,n,m,viz[NM];
void add(long x,long y)
{ lista *p=new lista;
  p->nod=y;
  p->urm=g[x];
  g[x]=p;
}
void dfs(long k)
{ lista *p=new lista;
  viz[k]=1;
  for (p=g[k];p;p=p->urm)
	 if (!viz[p->nod])
		dfs(p->nod);
}
int main()
{ ifstream f("dfs.in");
  ofstream g("dfs.out");
  f>>n>>m;
  long i,x,y;
  for (i=1;i<=m;i++)
	{ f>>x>>y;
	  add(x,y);
	  add(y,x);
	}
  for (i=1;i<=n;i++)
	if (!viz[i])
		{ nr++;
		  dfs(i);
		}
  g<<nr;
  f.close();
  g.close();
  return 0;
}