Cod sursa(job #3256210)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 13 noiembrie 2024 19:54:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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 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);
  }

  int cc = 0;
  vector<int> dist(n + 1, -1);
  for (int i = 1; i <= n; ++i) {
    if (dist[i] != -1)
      continue;

    queue<int> q;
    dist[i] = ++cc, q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();

      for (int v : adj[u])
        if (dist[v] == -1)
          dist[v] = dist[u], q.push(v);
    }
  }

  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;
}