Cod sursa(job #2261339)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 16 octombrie 2018 10:23:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>

#define MAXN 100000

using namespace std;

vector<int>v[MAXN+5];
int f[MAXN+5];

void conexa( int p )
{
  if( !v[p].empty() )
  {
    f[p]=1;

    for( vector<int>::iterator it=v[p].begin();it!=v[p].end();it++ )
      if( f[*it]==0 )
        conexa(*it);
  }
}

int main()
{
  freopen( "dfs.in", "r", stdin );
  freopen( "dfs.out", "w", stdout );

  int n, m;

  scanf( "%d%d", &n, &m );

  for( int i=1;i<=m;i++ )
  {
    int x, y;

    scanf( "%d%d", &x, &y );

    v[x].push_back(y);
    v[y].push_back(x);
  }

  int c=0;

  for( int i=1;i<=n;i++ )
    if( f[i]==0 )
    {
      c++;

      conexa(i);
    }

  printf( "%d", c );

  return 0;
}