Cod sursa(job #3139709)

Utilizator ItsComplicatedMihai Ian ItsComplicated Data 1 iulie 2023 00:46:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

int components;
int nr_nodes, nr_edges;
int node1, node2;
vector<vector<int>> graph;
bitset<100002> is_node_visited;

void dfs(int node) {
  is_node_visited[node] = true;
  for(auto next_node: graph[node]) {
    if(!is_node_visited[next_node]) {
      dfs(next_node);
    }
  }
}

int main()
{
    ifstream fin("dfs.in");
    fin >> nr_nodes >> nr_edges;
    graph.resize(nr_nodes + 1);
    for(int i = 0; i < nr_edges; i++) {
      fin >> node1 >> node2;
      graph[node1].push_back(node2);
      graph[node2].push_back(node1);
    }
    fin.close();

    for(int node = 1; node <= nr_nodes; node++) {
      if(!is_node_visited[node]) {
        dfs(node);
        components ++;
      }
    }

    ofstream fout("dfs.out");
    fout << components << endl;
    fout.close();

    return 0;
}