Cod sursa(job #149103)

Utilizator mariaciPopa Marius Ionut mariaci Data 5 martie 2008 12:34:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>
int viz[100005];
long long n,nc,m;
typedef struct nod
{ int x;
  nod *next;
}*pNod;
pNod v[100005];
void add(int x,int y)
{ pNod p;
  p=new nod;
  p->x=x;
  p->next=v[y];
  v[y]=p;
}
void citire()
{ freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  scanf("%lld%lld",&n,&m);
  long long x,y,i;
  for(i=1;i<=m;i++)
     { scanf("%lld%lld",&x,&y);
       add(x,y);add(y,x);
     }
}
void df(int nod)
{ pNod p;
  viz[nod]=1;
  for(p=v[nod];p!=NULL;p=p->next)
      if(!viz[p->x])
	   df(p->x);
}
int main()
{ citire();
  int i;
  for(i=1;i<=n;i++)
     if(!viz[i])
       { nc++;
	 df(i);
       }
  printf("%lld\n",nc);
  return 0;
}