Hackerrank Journey To The Moon Solution

#include <iostream>
#include <vector>
#include <algorithm>
// #include <utility>
#include <string>
#include <bitset>
using namespace std;
vector<vector<int> > a(100001,vector<int>());
bitset<100001> visited;
unsigned long long int cc(int u){
    if(visited[u])return 0;
    unsigned long long int count=1;
    visited[u]=1;
    for(int i:a[u])
        count+=cc(i);
    return count;
}
int main(){
        int n,p;
        cin>>n>>p;
        for(int i=0;i<n;i++)
            a[i].clear();
        visited.reset();
        for(int i=0;i<p;i++){
            int x,y;
            cin>>x>>y;
            a[x].push_back(y);
            a[y].push_back(x);
        }
        unsigned long long int ans=0,sum=cc(0);
        {
            for(int i=1;i<n;i++){
                if(!visited[i]){
                    unsigned long long int tmp=cc(i);
                    // cout<<i<<' '<<numcity<<' ';
                    ans+=sum*tmp;
                    sum+=tmp;
                }
            }
        }
        cout<<ans<<endl;
}

Comments