908 - Re-connecting Computer Sites Solution

Problem Link: here

Description: 

একটা গ্রাফের সাথে আরও কিছু edge যুক্ত করা হলো।পুরাতন ও নতুন গ্রাফ দুইটার জন্য প্রতিটা vertex ভিজিটের মিনিমাম cost (MST) বের করতে হবে।

Solution:

প্রথম গ্রাফের জন্য MST দেয়াই আছে । ওখান থেকে সবগুলার cost যোগ করে টোটাল cost পাওয়া যাবে।

আর দ্বিতীয় গ্রাফের জন্য MST বের করে cost হিসাব করতে হবে। সতর্কতা  1 ≤ N ≤ 1000000 

Code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pip pair<int,pii>
vector<pip> adj;
int par[2200000],sz[2200000];
int n,edge;
struct union_find{
    union_find(int n)
    {
        for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
    }
    int root(int a)
    {
        if (par[a]==a) return a;
        else return par[a] = root(par[a]);
    }
    bool isSame(int a,int b)
    {
        return root(a)==root(b);
    }
    void make_union(int a,int b)
    {
        int i = root(a);
        int j = root(b);
        if (i==j) return;
         if(sz[i] < sz[j])
        {
            par[i] = j;
            sz[j] += sz[i];
        }
        else
        {
            par[j] = i;
            sz[i] += sz[j];
        }
    }
};
long long int Kruskal()
{
    long long int total=0;
    union_find UF(n);
    int tt=0;
    for (int i=0;i<adj.size();i++)
    {
        int u = adj[i].second.first;
        int v = adj[i].second.second;
        int cost = adj[i].first;
        if (!UF.isSame(u,v))
        {
            UF.make_union(u,v);
            total+=cost;
            tt++;
        }
        if (tt==n-1) break;
    }
    return total;
}
int main()
{
    int t=0;
    while(scanf("%d",&n)==1)
    {
        long long int total = 0;
        int i;
        for (i=0;i<n-1;i++)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            total+=cost;
        }
        int e1;
        scanf("%d",&e1);
        for (i=0;i<e1;i++)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            adj.push_back(pip(cost,pii(u,v)));
        }
        int e2;
        scanf("%d",&e2);
        for (i=0;i<e2;i++)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            adj.push_back(pip(cost,pii(u,v)));
        }
        edge = e1+e2;
        sort(adj.begin(),adj.end());
        long long int total2 = Kruskal();
        if (t!=0) puts("");

        printf("%lld\n",total);
        printf("%lld\n",total2);
        if (t!=0) cin.ignore();
        t++;
        adj.clear();
    }
    return 0;
}