Josif_tepe

Untitled

Mar 18th, 2026
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int maxn=1e5+1;
  5. vector<int> v[maxn];
  6. int main()
  7. {
  8.     int n,r;
  9.     cin>>n>>r;
  10.     for(int i=0;i<r;i++)
  11.     {
  12.         int x,y;
  13.         cin>>x>>y;
  14.         v[x].push_back(y);
  15.         v[y].push_back(x);
  16.     }
  17.     vector<bool> visited(n, false);
  18.     long long res=0,sum=0;
  19.     for(int i=0;i<n;i++)
  20.     {
  21.         if(!visited[i])
  22.         {
  23.             queue<int> q;
  24.             q.push(i);
  25.             visited[i]=true;
  26.             int size=0;
  27.             while(!q.empty())
  28.             {
  29.                 int node=q.front();
  30.                 q.pop();
  31.                 size++;
  32.                 for(int x:v[node])
  33.                 {
  34.                     if(!visited[x])
  35.                     {
  36.                         visited[x]=true;
  37.                         q.push(x);
  38.                     }
  39.                 }
  40.             }
  41.             res+=(long long)size*sum;
  42.             sum+=size;
  43.         }
  44.     }
  45.     cout<<res;
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment