Cod sursa(job #2195438)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 16 aprilie 2018 13:30:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in ("dfs.in");
ofstream out ("dfs.out");

int const nmax = 100000;
vector < int > g[5 + nmax];
int seen[5 + nmax];

void flood(int node){
  seen[node] = 1;
  for(int h = 0 ; h < g[node].size() ;h++){
    int to = g[node][h];
    if(seen[to] == 0)
      flood(to);
  }
}
int main()
{
  int n , m;
  in >> n >> m;
  for(int i = 1 ; i <= m ;i++){
    int x , y;
    in >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int sum = 0;
  for(int i = 1 ; i <= n ;i++)
    if(seen[i] == 0){
      flood(i);
      seen[i] = 1;
      sum ++ ;
    }
  out << sum;
  return 0;
}