Cod sursa(job #2862768)

Utilizator DajaMihaiDaja Mihai DajaMihai Data 5 martie 2022 20:12:01
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>

#define MAXX 100001

using namespace std;

struct graphs{
  int subset;
  vector <int> edge;
};

graphs graph[MAXX];

void addEdge(int a, int b){
  graph[a].edge.push_back(b);
  graph[b].edge.push_back(a);
}

void dfs(int a, int noSubsets ){
  graph[a].subset = noSubsets;
  for (int b : graph[a].edge){
    if (graph[b].subset != noSubsets)
      dfs(b, noSubsets);
  }
}

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

int main(){
  int n, m;
  int a, b, noSubsets;
  in >> n >> m;
  for (int i = 0; i < m; i ++){
    in >> a >> b;
    addEdge (a, b);
  }

  noSubsets = 0;
  for (int i = 0; i < n; i ++){
    if (graph[i].subset == 0){
      dfs(i, ++noSubsets);
    }
  }
  out << noSubsets;
}