Cod sursa(job #276317)

Utilizator frumushelRadu Lucian Andrei frumushel Data 11 martie 2009 08:23:05
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<fstream.h>
struct nod{int inf;
	    nod *next;
	   }*L[100000];
int s[100000];
unsigned long n,m;
void df(int nodul)
{
 s[nodul]=1;
 while(L[nodul])
 {
    if(s[L[nodul]->inf]==0)
	  df(L[nodul]->inf);
   L[nodul]=L[nodul]->next;
 }
}
int main()
{long i,j;
 int nr=1;
 nod *p;
 ifstream f("dfs.in");
 ofstream g("dfs.out");
 f>>n>>m;
 for(i=1;i<=m;i++)
 {
  f>>i>>j;
  p=new nod;
  p->inf=i;
  p->next=L[j];
  L[j]=p;
  p=new nod;
  p->inf=j;
  p->next=L[i];
  L[i]=p;
 }

df(1);
for(i=1;i<=n;i++)
{
 if(s[i]!=1){nr++;
	     df(i);
	    }
 }
 g<<nr;
return 0;
}