Advertisement
Josif_tepe

Untitled

Nov 21st, 2022
575
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <set>
  7. #include <map>
  8. using namespace std;
  9. using namespace std;
  10. vector<int>graph[100005];
  11. int main() {
  12.  
  13.  
  14. int n, m;
  15. cin>>n>>m;
  16.  
  17. for(int i=0; i<m; i++){
  18.     int a, b;
  19.     cin>>a>>b;
  20.     graph[a].push_back(b);
  21.     graph[b].push_back(a);
  22.     }
  23.  
  24. bool visited[n];
  25. memset(visited, false, sizeof visited);
  26. queue<int>q;
  27.  
  28.  
  29.  
  30. long long result=0;
  31.  
  32.  
  33.  
  34.     for(int j=0; j<n; j++){
  35.         int counter=0;
  36.        
  37.         if(visited[j]!=true){
  38.             q.push(j);
  39.             visited[j] = true;
  40.            
  41.            
  42.            
  43.             while(!q.empty()){
  44.                 int cs=q.front();
  45.                 q.pop();
  46.                
  47.                
  48.                
  49.                 for(int i=0; i<graph[cs].size(); i++){
  50.                     if(visited[graph[cs][i]]==false){
  51.                         q.push(graph[cs][i]);
  52.                        
  53.                         visited[graph[cs][i]]=true;
  54.                     }
  55.                    
  56.                    
  57.                 }
  58.                 counter++;
  59.                
  60.             }
  61. //            cout << counter << endl;
  62.             result += counter * (n - counter);
  63.         }
  64.     }
  65.  
  66. cout<<result / 2;
  67.  
  68.  
  69.  
  70.  
  71.     return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement