Advertisement
Josif_tepe

Untitled

Mar 21st, 2025
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <queue>
  6. using namespace std;
  7. typedef long long ll;
  8. const int maxn = 1e5 + 100;
  9. vector<int> graph[maxn];
  10.  
  11. int main() {
  12.     int n, m;
  13.     cin >> n >> m;
  14.    
  15.     for(int i = 0; i < m; i++) {
  16.         int a, b;
  17.         cin >> a >> b;
  18.        
  19.         graph[a].push_back(b);
  20.         graph[b].push_back(a);
  21.     }
  22.    
  23.     vector<bool> visited(n, false);
  24.    
  25.     ll res = 0;
  26.     for(int i = 0; i < n; i++) {
  27.         if(!visited[i]) {
  28.             ll size_of_component = 0;
  29.            
  30.             queue<int> q;
  31.             q.push(i);
  32.             visited[i] = true;
  33.             while(!q.empty()) {
  34.                 int node = q.front();
  35.                 q.pop();
  36.                
  37.                 size_of_component++;
  38.                
  39.                 for(int i = 0; i < (int) graph[node].size(); i++) {
  40.                     int neighbour = graph[node][i];
  41.                     if(!visited[neighbour]) {
  42.                         visited[neighbour] = true;
  43.                         q.push(neighbour);
  44.                     }
  45.                 }
  46.             }
  47.             res += size_of_component * (n - size_of_component);
  48.         }
  49.     }
  50.    
  51.     cout << res / 2<< endl;
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement