Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define nl "\n"
- void files(){
- ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- }
- void solve(){
- int n,m; cin>>n>>m;
- vector<vector<int>>adj(n+1);
- for(int i=0; i<m; i++){
- int u,v; cin>>u>>v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- vector<bool>vis(n+1, false);
- ll ans = 0;
- for(int i=1;i<=n;i++){
- if(vis[i]) continue;
- queue<int>q;
- q.push(i);
- vis[i] = true;
- ll total = 0;
- while(!q.empty()){
- ll sz = q.size();
- ans += max(0LL,(total-1))*sz;
- ans += sz*(sz-1)/2;
- total += sz;
- while(sz--){
- int node = q.front();
- q.pop();
- for(auto& child: adj[node]){
- if(!vis[child]){
- vis[child] = true;
- q.push(child);
- }
- }
- }
- }
- }
- cout<<ans<<nl;
- }
- int main(){
- files();
- int t = 1;
- // cin>>t;
- while(t--) solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement