Advertisement
Ahmed_Negm

Untitled

Apr 20th, 2024
812
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define nl "\n"
  6.  
  7. void files(){
  8.     ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
  9.     #ifndef ONLINE_JUDGE
  10.         freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  11.     #endif
  12. }
  13.  
  14.  
  15. void solve(){
  16.     int n,m; cin>>n>>m;
  17.     vector<vector<int>>adj(n+1);
  18.     for(int i=0; i<m; i++){
  19.         int u,v; cin>>u>>v;
  20.         adj[u].push_back(v);
  21.         adj[v].push_back(u);
  22.     }
  23.  
  24.  
  25.     vector<bool>vis(n+1, false);
  26.     ll ans = 0;
  27.     for(int i=1;i<=n;i++){
  28.         if(vis[i]) continue;
  29.         queue<int>q;
  30.         q.push(i);
  31.         vis[i] = true;
  32.         ll total = 0;
  33.         while(!q.empty()){
  34.             ll sz = q.size();
  35.             ans += max(0LL,(total-1))*sz;
  36.             ans += sz*(sz-1)/2;
  37.             total += sz;
  38.             while(sz--){
  39.                 int node = q.front();
  40.                 q.pop();
  41.                 for(auto& child: adj[node]){
  42.                     if(!vis[child]){
  43.                         vis[child] = true;
  44.                         q.push(child);
  45.                     }
  46.                 }
  47.             }
  48.         }
  49.  
  50.     }
  51.  
  52.     cout<<ans<<nl;
  53.  
  54. }
  55.  
  56. int main(){
  57.     files();
  58.     int t = 1;
  59.     // cin>>t;
  60.     while(t--) solve();
  61.  
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement