Cod sursa(job #408125)

Utilizator me_andyAvramescu Andrei me_andy Data 2 martie 2010 20:53:29
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream.h>
#define max 100100
 ifstream f("dfs.in");
 ofstream g("dfs.out");
 long uz[max],st[max],j,i,n,m,c,x,y;

typedef struct nod
{
 int info;
 nod *urm;
} *pNod;

pNod a[max];

void add(pNod &prim,int inf)
{
 pNod x=new nod;
 x->info=inf;
 x->urm=prim;
 prim=x;
}

int main()
{
 f>>n>>m;
 for(i=1;i<=n;i++)
 {
  f>>x>>y;
  add(a[x],y);
  add(a[y],x);
 }
 c=0;
 for(j=1;j<=n;j++)
 if(uz[j]==0)
 {
 c++;
 st[1]=j;
 uz[j]=c;
 i=1;
  while(i)
  {
   pNod prim=a[st[i]];
   i--;
   while(prim)
   {
    if(uz[prim->info]==0)
    {
     st[++i]=prim->info;
     uz[st[i]]=c;
    }
    prim=prim->urm;
   }
  }
 }
 g<<c;
 return 0;
}