Advertisement
clown1337

Untitled

Mar 23rd, 2023
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.66 KB | None | 0 0
  1. const int N = 100100;
  2. vector <vector <int>> g(N);
  3. bool used[N];
  4.  
  5. void dfs(int v) {
  6. used[v] = true;
  7. for (int i = 0; i < g[v].size(); ++i) {
  8. int u = g[v][i];
  9. if (!used[u]) {
  10. dfs(u);
  11. }
  12. }
  13. }
  14.  
  15. signed main() {
  16. ios_base::sync_with_stdio(false);
  17. cin.tie(NULL);
  18. int n, m; cin >> n >> m;
  19. for (int i = 0; i < m; ++i) {
  20. int u1, u2; cin >> u1 >> u2;
  21. g[u1].push_back(u2);
  22. g[u2].push_back(u1);
  23. }
  24. int connect = 0;
  25. for (int i = 1; i <= n; ++i) {
  26. if (!used[i]) {
  27. dfs(i);
  28. connect++;
  29. }
  30. }
  31. cout << connect << '\n';
  32. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement