Cod sursa(job #238330)

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

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;
 }