Cod sursa(job #3166420)

Utilizator BogdanPPBogdan Protopopescu BogdanPP Data 8 noiembrie 2023 18:53:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

vector<vector<int>>graph(100001);
vector<bool>visited(100001, false);

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

int main()
{
  int n, m, cnt=0;
  fin >> n >> m;

  for (int i=0; i<m; i++)
  {
    int a, b;
    fin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  for (int i=1; i<=n; i++)
    if (!visited[i])
    {
      cnt++;
      dfs(i);
    }
  fout << cnt;
  return 0;
}