Cod sursa(job #3256211)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 13 noiembrie 2024 20:02:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;
using ld = long double;

void dfs(int node, vector<bool> &visited, const vector<vector<int>> &adj) {
  visited[node] = true;
  for (int neigh : adj[node])
    if (!visited[neigh])
      dfs(neigh, visited, adj);
}

void solve() {
  int n, m;
  cin >> n >> m;

  vector<vector<int>> adj(1 + n);
  for (int u, v, i = 0; i < m; ++i) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  vector<bool> visited(1 + n, false);
  int cc = 0;
  for (int i = 1; i <= n; ++i)
    if (!visited[i])
      dfs(i, visited, adj), ++cc;
  cout << cc << endl;
}

int main() {
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}