Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn=1e5+1;
- vector<int> v[maxn];
- int main()
- {
- int n,r;
- cin>>n>>r;
- for(int i=0;i<r;i++)
- {
- int x,y;
- cin>>x>>y;
- v[x].push_back(y);
- v[y].push_back(x);
- }
- vector<bool> visited(n, false);
- long long res=0,sum=0;
- for(int i=0;i<n;i++)
- {
- if(!visited[i])
- {
- queue<int> q;
- q.push(i);
- visited[i]=true;
- int size=0;
- while(!q.empty())
- {
- int node=q.front();
- q.pop();
- size++;
- for(int x:v[node])
- {
- if(!visited[x])
- {
- visited[x]=true;
- q.push(x);
- }
- }
- }
- res+=(long long)size*sum;
- sum+=size;
- }
- }
- cout<<res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment