এইটা Union
Find টপিকস রিলেটেড
পুরো
কোড সবার নিচে
দেখা
যাবে দেওয়া থাকলো ৫ টা মান
ইনপুটঃ-
৫ ২ //৫ হল ৫ টা মান আর ২ হল ২ টা বন্ধুর
লিস্ট
৮ ৫ ৩ ৪ ২ // এইগুলো হল পজিশন অনুযায়ী এদের ওয়েট যেমন ১
এর ৮,২ এর ৫ ,৩ এর ৩ ,৪ এর ৪ ,৫ এর ২
১ ৪ // ৪ ও ১ বন্ধু
৪ ৫ // ৪ ও ৫ বন্ধু
আউটপুটঃ-১০
এখন ১ ৪
৫ একটা দল ,২ একটা দল,৩ একটা দল
এদের
মধ্যে সব গুলো দলের মিনিমাম ওয়েট এর যোগফল কত?
উত্তর=১০
কারণ
১,৪,৫ এই দলের মিনিমাম ২+২ এর দলের ৫+৩ এর দলের ৩=১০
একটা
কোড যদি করা থাকে সবার প্যারেন্ট কে এইবার মিনিমাম ওয়েট কিভাবে পাবো?
সেইটার
কোডঃ
for(i=1;i<=n;i++)
{
par[i]=Find(i);
st.insert(par[i]);
mn[par[i]]=min(mn[par[i]],ar[i]);
cout<<mn[par[i]]<<endl;
}
set<long long >::iterator it;
for(it=st.begin(); it!=st.end(); it++)
{
ans+=mn[*it];
}
cout<<ans<<endl;
পুরো
কোডঃ-
#include <bits/stdc++.h>
using namespace std;
//long long vis[100010],ar[100010];
//vector<long long>vec[100010];
long long n,k;
long long par[100010],ar[100010],mn[100005];
long long Find(long long xx)
{
if(par[xx]==xx)
return xx;
return
par[xx]=Find(par[xx]);
}
void make_union(long long x,long long y)
{
par[Find(y)]=Find(x);
}
set<long long>st;
main()
{
//long k;
cin>>n>>k;
{
long long
i,u1,v1,ans=0;
for(i=1;
i<=n; i++)
{
cin>>ar[i];
mn[i]=ar[i];
par[i]=i;
}
for(i=1;
i<=k; i++)
{
cin>>u1>>v1;
make_union(u1,v1);
}
for(i=1;i<=n;i++)
{
par[i]=Find(i);
st.insert(par[i]);
mn[par[i]]=min(mn[par[i]],ar[i]);
cout<<mn[par[i]]<<endl;
}
set<long long >::iterator it;
for(it=st.begin(); it!=st.end(); it++)
{
ans+=mn[*it];
}
cout<<ans<<endl;
}
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন