- এই সমস্যা তে আমাদের গ্রাফে যদিগুলি সাইকেল আছে প্রত্যেক টা সাইকেলে যে edge আছে তাদের মধ্যে ম্যাক্স ওয়েট ধারি এজ এর ওয়েট গুলিকে প্রিন্ট করেত হবে । অর্থাৎ আমাদের গ্রাফে যদি ২ টা সাইকেল থাকে তবে ঐ ২ সাইকেল এজ গুলির মধ্যে ম্যাক্স ২ টা প্রিন্ট করতে হবে । [ ২য় ইনপুট লক্ষণীয় ]
- আমরা যদি Kruskal Algorithm ব্যাবহার করি তবে খুব সহজেই এই সমস্যার সমাধান করতে পারব ।
- Kruskal এ প্রত্যেক বার যখন নতুন কোন এজ আমাদের Spanning Tree তে যোগ করতে যাব তখন দেখব তাদের Node দুইটির ফাদার একই কি না ? যদি ফাদার একই হয় তার মানে এই এজটা নিলে আমাদের সাইকেল তৈরি হবে । আর আমাদের এই এজের ওয়েট ই দরকার ।
- ওয়েট গুলো কে আমরা অন্য একটা ভেক্টরে জমা করা রাখব ।
- শেষে যদি দেখা যায় আমাদের ভেক্টর টি ফাকা রয়ে গেছে তার মানে আমাদের গ্রাফে কোন সাইকেল নেই । এই অবস্থায় আমাদের কে forest প্রিন্ট করতে হবে ।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
হ্যাপি কোডিং :D
Comments
Post a Comment