Cod sursa(job #211070)

Utilizator Mishu91Andrei Misarca Mishu91 Data 30 septembrie 2008 17:14:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>

typedef struct nod
{
   int n;
   nod *next;
}*list;

list v[1000];
int N,M,cnt,viz[1000];

void add(list &x, int y)
{
   list p = new nod;
   p -> n = y;
   p -> next  = x;
   x = p;
}

void citire()
{
  int a,b;
  scanf("%d %d",&N,&M);
  for(int i = 1; i <= M; i++)
  {
     scanf("%d %d",&a, &b);
     add(v[a],b);
     add(v[b],a);
  }
}

void dfs(int k)
{
   viz[k] = 1;
   for(list p = v[k]; p != NULL; p = p -> next)
   if(!viz[p -> n])
   dfs(p -> n);
}

void solve()
{
   for(int i = 1; i <= N; i++)
      if(!viz[i])
      {
	 cnt++;
	 dfs(i);
      }
   printf("%d\n",cnt);
}

int main()
{
    freopen("date.in","rt",stdin);
    freopen("date.out","wt",stdout);
    citire();
    solve();
    return 0;
}