Cod sursa(job #2799229)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 12 noiembrie 2021 18:00:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <ctype.h>

// Program de Mircea Rebengiuc
// inceput pe 2021.11.12

#define MAXN 100000
#define MAXM 200000
#define NIL -1

int viz[MAXN];
int list[MAXN];
int adj[MAXM];
int next[MAXM];

void dfs( int root ){
  int i = list[root];

  viz[root] = 1;

  while( i != NIL ){
    if( !viz[adj[i]] )
      dfs(adj[i]);

    i = next[i];
  }
}

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit(ch = fgetc(fin)) );
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n;
}

int main(){
  fin  = fopen("dfs.in",  "r");
  fout = fopen("dfs.out", "w");

  int n, m, i, a, b, ans;

  n = fgetint();
  for( i = 0 ; i < n ; i++ )
    list[i] = NIL;

  i = 0;
  for( m = fgetint() ; m-- ; ){
    a = fgetint() - 1;
    b = fgetint() - 1;

    adj[i] = b;
    next[i] = list[a];
    list[a] = i++;

    adj[i] = a;
    next[i] = list[b];
    list[b] = i++;
  }

  ans = 0;
  for( i = 0 ; i < n ; i++ )
    if( !viz[i] ){
      ans++;
      dfs(i);
    }

  fprintf(fout, "%d\n", ans);

  fclose(fin);
  fclose(fout);
  return 0;
}