Cod sursa(job #172211)

Utilizator cristi8Constantin-Cristian Balas cristi8 Data 5 aprilie 2008 22:30:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.21 kb
/*
  Cristi Balas,
  Facultatea de Matematica si Informatica, Universitatea Bucuresti
  cristi8 [at] gmail.com
*/
#include <stdio.h>
#include <stdlib.h>


typedef struct nod // un nod din lista de vecini
{
  int vecin;
  struct nod *nxt; // next :)
} nod;

#define NMAX 100001

int n;
nod *lv[NMAX]; // lista de vecini a fiecarui nod
char marcat[NMAX];

void adauga_vecin(int cui, int pe_cine)
{
  nod *q = malloc(sizeof(nod));
  q->vecin = pe_cine;
  // q se leaga de inceputul listei de vecini (asa e mai simplu, si nu conteaza ordinea)
  q->nxt = lv[cui];
  lv[cui] = q;
}

void read_data()
{
  int m; // nu e important nr de muchii pt tot programul
  int n1, n2; // capetele unei muchii citite
  scanf("%d%d", &n, &m);
  while(m--)
  {
    scanf("%d%d", &n1, &n2);
    adauga_vecin(n1, n2);
    adauga_vecin(n2, n1);
  }
}

void df(int nod_id)
{
  nod *q;
  marcat[nod_id] = 1;
  for(q = lv[nod_id]; q; q = q->nxt)
    if(!marcat[q->vecin])
      df(q->vecin);
}

void solve()
{
  int i, count = 0;
  for(i = 1; i <= n; i++)
    if(!marcat[i])
    {
      df(i);
      count++;
    }
  printf("%d\n", count);
}

int main()
{
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);
  read_data();
  solve();
  return 0;
}