HackerEarth Connecting the special nodes problem solution

In this HackerEarth Connecting the Special nodes problem solution You are given a graph of N nodes. The graph consists of connected components. Some of the connected components contain a special node and each component contains at most one special node. You are required to maximize the number of edges in the given graph such that it follows these constraints:

No self-loop or multiple edges should be present
No connected components with more than one special node should be present
Each node in the graph should belong to a component with exactly one special node

If you add an edge between two nodes that belong to the same component in the graph, then the total cost involved is 0. Whereas, if you connect two nodes that belong to different components, then the cost is equal to the product of the sizes of both the components.

Your task is to maximize the number of new edges in the graph and calculate the minimum cost that will be involved in performing the required task.

HackerEarth Connecting the special nodes problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define reset(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
#define endl "n"
#define eps 0.00000001
#define check(a , b , c) assert(a >= b && a <= c)
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int u[200001];
int v[200001];
int w[200001];
vector<int> graph[200001];
bool visit[200001];
int sz = 0;
int eg = 0;
int deg[200001];
vector<pair<int,int> > watered;
vector<pair<int,int> > dry;
void dfs(int node)
    {
        sz++;
        visit[node] = 1;
        eg += deg[node];
        for(int i: graph[node])
            {
                if(visit[i] == 0)
                    {
                        visit[i] = 1;
                        dfs(i);
                    }
            }
    }
int main()
    {
        ios_base::sync_with_stdio(0);
        int n , m , k;
        cin >> n >> m >> k;
        for(int i = 0; i < m; i++)
            {
                cin >> u[i] >> v[i];
                graph[u[i]].push_back(v[i]);
                graph[v[i]].push_back(u[i]);
                ++deg[u[i]];
                ++deg[v[i]];
            }
        for(int i = 0; i < k; i++)
            cin >> w[i];
        LL ans1 = 0 , ans2 = 0;
        LL maxsz = 0;
        for(int i = 0; i < k; i++)
            {
                sz = 0;
                eg = 0;
                if(visit[w[i]] == 1)
                    continue;
                dfs(w[i]);
                maxsz = max(maxsz , (LL)sz);
                eg /= 2;
                watered.push_back(make_pair(sz , eg));
                ans1 += (sz * (sz - 1)) / 2 - eg;
            }
        for(int i = 1; i <= n; i++)
            {
                if(visit[i] == 0)
                    {
                        sz = 0;
                        eg = 0;
                        dfs(i);
                        eg /= 2;
                        dry.push_back(make_pair(sz , eg));
                        ans1 += (sz * (sz - 1)) / 2 - eg;
                    }
            }
        sort(watered.begin() , watered.end());
    
        LL pre = 0 , cur = 0;
        for(int i = 0; i < dry.size(); i++)
            {
                ans2 = ans2 + pre * dry[i].first;
                ans1 += pre * dry[i].first;
                pre += dry[i].first;
            }
        
        ans2 += pre * maxsz;
        ans1 += pre * maxsz;
        cout << ans1 << " " << ans2;
                
    }

coding problems solutions