Cod sursa(job #2788431)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 25 octombrie 2021 17:53:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100000;

vector<int> graf[1 + NMAX];

bool vizitat[1 + NMAX];

void dfs(int nodCrt)
{
  vizitat[nodCrt] = true;

  for (int i = 0; i < graf[nodCrt].size(); i++)
  {
    int vecin = graf[nodCrt][i];

    if (!vizitat[vecin])
      dfs(vecin);
  }
}

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

  int n, m;
  in >> n >> m;

  for (int j = 1; j <= m; j++)
  {
    int x, y;
    in >> x >> y; /// muchie neorientata x->y si x<-y

    graf[x].push_back(y);
    graf[y].push_back(x); /// asta pentru graf neorientat
  }

  int nrCompConexe = 0;

  for (int i = 1; i <= n; i++)
  {
    if (!vizitat[i])
    {
      nrCompConexe++;
      dfs(i);
    }
  }

  out << nrCompConexe << '\n';

  return 0;
}