[ 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