Cod sursa(job #2001761)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 17 iulie 2017 18:06:45
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <stdio.h>
#define maxn 1000

using namespace std;

int ll[maxn][maxn];
int co[maxn];
int t[maxn];

void dfs ( int n ) {
  t[n] = 1;

  for ( int i = 0; i < co[n]; i++ )
    if ( t[ll[n][i]] == 0 )
      dfs ( ll[n][i] );
}

int main () {
  ifstream fin ( "dfs.in" );
  ofstream fout ( "dfs.out" );

  int n, m;

  fin >> n >> m;

  int i, a, b;

  for ( i = 0; i < m; i++ ) {
    fin >> a >> b;

    a--; b--;

    ll[a][co[a]++] = b;
    ll[b][co[b]++] = a;
  }

  int nc = 0;

  for ( i = 0; i < n; i++ )
    if ( t[i] == 0 ) {
      dfs ( i );
      nc++;
    }

  fout << nc << '\n';

  fin.close();
  fout.close();

  return 0;
}