Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <cstring>
- #include <set>
- #include <map>
- using namespace std;
- using namespace std;
- vector<int>graph[100005];
- int main() {
- int n, m;
- cin>>n>>m;
- for(int i=0; i<m; i++){
- int a, b;
- cin>>a>>b;
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- bool visited[n];
- memset(visited, false, sizeof visited);
- queue<int>q;
- long long result=0;
- for(int j=0; j<n; j++){
- int counter=0;
- if(visited[j]!=true){
- q.push(j);
- visited[j] = true;
- while(!q.empty()){
- int cs=q.front();
- q.pop();
- for(int i=0; i<graph[cs].size(); i++){
- if(visited[graph[cs][i]]==false){
- q.push(graph[cs][i]);
- visited[graph[cs][i]]=true;
- }
- }
- counter++;
- }
- // cout << counter << endl;
- result += counter * (n - counter);
- }
- }
- cout<<result / 2;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement