Cod sursa(job #238325)

Utilizator zbarniZajzon Barna zbarni Data 1 ianuarie 2009 21:10:45
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdlib.h>
#include<stdio.h>
#define nmax 100003
int *a[nmax];
int sz,n,m,viz[nmax];
void bfs(int x)
 {
  int list[nmax]={0};
  int e,v,i;
  e=v=0;
  list[e]=x;
  viz[x]=1;
  while (e<=v)
   {
    x=list[e++];
    for (i=1;i<=a[x][0];i++)
      if (!viz[a[x][i]])
       {
	list[++v]=a[x][i];
	viz[a[x][i]]=1;
       }
   }
 }

int main()
 {
  freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  int i,x,y;
  scanf("%d %d",&n,&m);
  for (i=1;i<=n;i++)
    {
     a[i]=(int *)realloc(a[i],sizeof(int));
     a[i][0]=0;
    }
  for (i=1;i<=m;i++)
   {
    scanf("%d %d",&x,&y);
    a[x][0]++;
    a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
    a[x][a[x][0]]=y;
    a[y][0]++;
    a[y]=(int *)realloc(a[y],(a[y][0]+1)*sizeof(int));
    a[y][a[y][0]]=x;
   }
  for (i=1;i<=n;i++)
   {
    if (!viz[i])
     {
      ++sz;
      bfs(i);
     }
   }
  printf("%d\n",sz);
  return 0;
 }