Skip to main content

[ UVa ] 11747 - Heavy Cycle Edges

  • এই সমস্যা তে আমাদের গ্রাফে যদিগুলি সাইকেল আছে প্রত্যেক টা সাইকেলে যে edge আছে তাদের মধ্যে ম্যাক্স ওয়েট ধারি এজ এর ওয়েট গুলিকে প্রিন্ট করেত হবে । অর্থাৎ আমাদের গ্রাফে যদি ২ টা সাইকেল থাকে তবে ঐ ২ সাইকেল এজ গুলির মধ্যে ম্যাক্স ২ টা প্রিন্ট করতে হবে । [ ২য় ইনপুট লক্ষণীয় ] 
  •   আমরা যদি Kruskal Algorithm ব্যাবহার করি তবে খুব সহজেই এই সমস্যার সমাধান করতে পারব । 
  • Kruskal এ প্রত্যেক বার যখন নতুন কোন এজ আমাদের Spanning Tree তে যোগ করতে যাব তখন  দেখব তাদের Node দুইটির ফাদার একই কি না ?  যদি ফাদার একই হয় তার মানে এই এজটা নিলে আমাদের সাইকেল তৈরি হবে । আর আমাদের এই এজের ওয়েট ই দরকার । 
  • ওয়েট গুলো কে আমরা অন্য একটা ভেক্টরে জমা করা রাখব । 
  • শেষে যদি দেখা যায় আমাদের ভেক্টর টি ফাকা রয়ে গেছে তার মানে আমাদের গ্রাফে কোন সাইকেল নেই । এই অবস্থায় আমাদের কে forest প্রিন্ট করতে হবে । 
কোড :
/**
* Problem : 11747 - Heavy Cycle Edges.
* Verdict : Accepted.
* Time : 0.000 ms.
* Write : Mehadi Hasan Menon.
* Date : 01.01.2017.
**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
int u, v, w;
bool operator < (const edge &p) const {
return w < p.w;
}
};
const int mx = 1005;
int father[mx];
vector <int> max_weight;
vector <edge> edge_list;
int find_rep(int r)
{
if(father[r] == r) {
return r;
}
father[r] = find_rep(father[r]);
return father[r];
}
void mst_kruskal(int n)
{
// initialize father 1st time.
for(int i = 0; i < n; i++) {
father[i] = i;
}
edge new_edge;
int sz = edge_list.size();
for(int i = 0; i < sz; i++) {
new_edge = edge_list[i];
int u = find_rep(new_edge.u);
int v = find_rep(new_edge.v);
if(u == v) {
// we meet with cycle. so take the weight of the new edge.
max_weight.push_back(new_edge.w);
}
else {
// set u as father of v.
father[v] = u;
}
}
}
int main()
{
freopen("input.txt", "r+", stdin);
int n, m, u, v, w;
while(scanf("%d %d", &n, &m))
{
if(n == 0 && m == 0) {
break;
}
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
edge get;
get.u = u;
get.v = v;
get.w = w;
edge_list.push_back(get);
}
sort(edge_list.begin(), edge_list.end());
mst(n);
int sz = max_weight.size();
if(sz == 0) {
cout << "forest" << endl;
}
else {
for(int i = 0; i < sz; i++) {
if(i > 0) {
printf(" ");
}
printf("%d", max_weight[i]);
}
puts("");
}
max_weight.clear();
edge_list.clear();
}
return 0;
}
view raw 11747.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং :D

Comments

Popular posts from this blog

উবুন্টুতে রুট পাসওয়ার্ড ভুলে তা রিকভার করার উপায় ।

যদি কেউ রুট পাসওয়ার্ড ভুলে যান তাহলে নিচের কাজ গুলো করে নতুন পাসওয়ার্ড সেট করতে পারবেন: প্রথমে পিসি রিস্টার্ট দিন । দিয়ে UP/DOWN করে kernel version সিলেক্ট করে e চাপুন । ব্ল্যাক Screen আসবে এবার একটা Space দিয়ে লিখুন “Single” [ Enter ] এরপর b চাপুন ফলাফল : লিনাক্সের Single user Mood এ চলে আসছেন । এখন লিখুন passwd root [ Enter ] এখন নতুন পাসওয়ার্ড খানা টাইপ করেন [ এন্টার ] আবার টাইপ করেন [ এন্টার ] কাজ শেষ , এবার reboot টাইপ করেন । এখন নতুন পাসওয়ার্ড দিয়ে লগইন করেন। পুনশ্চ : যদি আপনার উইন্ডোজ এর সাথে ডুয়েল বুট করা থাকে তবে এই প্রক্রিয়া কাজ করবে না ।

Fix The BIOS in this system is not fully ACPI compliant in Windows 7

এই সমস্যা সমাধান করার জন্য আপনি নিচের ধাপ গুলো অনুসরণ করুন। ধাপ ১ :  আপানর  কম্পিউটার এ উইন্ডোজ এর ডিস্ক থেকে বুট করুন । নীচের মত উইন্ডো আসলে Shift + F10 চাপুন । এর ফলে কমান্ড প্রম্প্ট ওপেন হবে। ধাপ ২ : এখন CMD তে নিচের কমান্ড গুলি ধারবাহিক ভাবে লিখুন C: bootrec /FixMbr bootrec /FixBoot bootrec /RebuildBcd exit  এখানে  C হলো যে ড্রাইভ এ উইন্ডোজ দেয়া আছে।  আপনার যদি অন্য কোনো ড্রাইভ ( D, E, F, ..... ) এ উইন্ডোজ দেয়া থাকে তবে আপনাকে C এর জায়গায় সেই ড্রাইভ এর নাম লিখতে হবে।  উপরের সব কমান্ড যদি সঠিক ভাবে বিল্ড হয় তবে আপনি আপনার কম্পিউটার রিস্টার্ট দিন।  দেখবেন আপনার সমস্যা সমাধান হয়ে গেছে :D