Cod sursa(job #156585)

Utilizator AlxCojocaru Alexandru Alx Data 12 martie 2008 17:16:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <stdio.h>
struct graf
{
 int nod;
 graf *next;
};
graf *a[100001];
long n,m,x,y,cnx;
int viz[100001];
void dfs(long k)
{
 viz[k]=1;
 graf *q=a[k];
 while (q)
 {
  if (!viz[q->nod])
   dfs(q->nod);
  q=q->next;
 }
}
int main()
{
 freopen("dfs.in","r",stdin);
 freopen("dfs.out","w",stdout);
 scanf("%ld %ld\n",&n,&m);
 long i;
 for (i=0;i<m;i++)
 {
  scanf("%ld %ld\n",&x,&y);
  graf *q=new graf;
  q->nod=x;
  q->next=a[y];
  a[y]=q;
  q=new graf;
  q->nod=y;
  q->next=a[x];
  a[x]=q;
 }
 for (i=1;i<=n;i++)
  if (!viz[i])
  {
   dfs(i);
   cnx++;
  }
 printf("%ld\n",cnx);
 return 0;
}