Cod sursa(job #277665)

Utilizator alexandru92alexandru alexandru92 Data 11 martie 2009 20:41:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#include<string.h>
#define Nmax 100001
int n,nr;
struct nod
     {
      int info;
      nod *urm;
     };
typedef nod *Lista;
Lista L[Nmax],U[Nmax];
void Insert(Lista &prim,Lista p,int x)
   {
    Lista q=new nod;
    q->info=x;
    if(prim) { q->urm=p->urm; p->urm=q;}
      else { q->urm=prim; prim=q;}
    }
void DFS();
int main()
  {int m,i,x,y;
   freopen("dfs.in","rt",stdin);
   freopen("dfs.out","wt",stdout);
   scanf("%d %d",&n,&m);
   for(i=1;i<=m;++i)
      {scanf("%d %d",&x,&y);
       if(L[x]) Insert(L[x],U[x],y),U[x]=U[x]->urm;
         else Insert(L[x],NULL,y),U[x]=L[x];
       if(L[y]) Insert(L[y],U[y],x),U[y]=U[y]->urm;
         else Insert(L[y],NULL,x),U[y]=L[y];
       }
   DFS();
   printf("%d",nr);
   return 0;
  }
bool uz[Nmax];
void DFS()
   {
    Lista p;
    int v[Nmax],st,x,i;
    for(i=1;i<=n;++i)
        if(!uz[i])
          {st=1; v[1]=i; uz[i]=1;
           while(st)
                {
                 x=v[st--];
                 for(p=L[x];p;p=p->urm)
                 if(!uz[p->info]) v[++st]=p->info,uz[p->info]=1;
                }
           nr++;
           }
   }