Advertisement
Josif_tepe

Untitled

Feb 22nd, 2024
979
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. const int maxn = 1e5 + 10;
  6. vector<int> graph[maxn];
  7. bool visited[maxn];
  8. int size_of_island;
  9. void dfs(int node) {
  10.     visited[node] = true;
  11.     size_of_island++;
  12.     for(int i = 0; i < (int) graph[node].size(); i++) {
  13.         int neighbour = graph[node][i];
  14.         if(!visited[neighbour]) {
  15.             dfs(neighbour);
  16.         }
  17.     }
  18. }
  19. int main() {
  20.     ios_base::sync_with_stdio(false);
  21.     int n, m;
  22.     cin >> n >> m;
  23.    
  24.     for(int i = 0; i < m; i++) {
  25.         int a, b;
  26.         cin >> a >> b;
  27.         graph[a].push_back(b);
  28.         graph[b].push_back(a);
  29.     }
  30.     for(int i = 0; i < n; i++) {
  31.         visited[i] = false;
  32.     }
  33.     long long res = 0;
  34.     for(int i = 0; i < n; i++) {
  35.         if(!visited[i]) {
  36.             size_of_island = 0;
  37.             dfs(i);
  38.             res += size_of_island * (n - size_of_island);
  39.         }
  40.     }
  41.     cout << res / 2 << endl;
  42.    
  43.     return 0;
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement