DSU(DISJOINT SET) || CodeForeces 479(DIV - 3)
Problem Link: E. Cyclic Components প্রব্লেম স্টেট্মেন্টঃ একটি আনডিরেক্টেড গ্রাফের নির্দিষ্ট সংখ্যক নোড এবং এজ দেয়া থাকবে। বের করতে হবে কতগুলা কানেক্টেড কম্পোনেন্টের মধ্যে সাইকেল আছে। বাই ডেফিনিশন একটি সাইকেলের মিনিমাম তিন টা এজ থাকতে হবে। অব্জারবেশনঃ একটি কানেক্টেড কম্পোনেন্ট তখনি সাইকেল হবে যখন এর প্রত্যেকটা নোডের এজের ডিগ্রি ২ হবে। অন্যথায় এটি সাইকল হবে না। যেমন- এই কানেক্টেড কম্পোনেন্টি কোন সাইকেল নয়। এখানে ৬ এবং ৭ নাম্বার নোডের এজের ডিগ্রি ১। সলিউশনঃ আমরা BFS করে প্রব্লেম টি ইজিলি সল্ভ করতে পারবো। কিন্তু এখানে অন্য একটি ডাটা স্ট্রাকচারের মাধ্যমে প্রব্লেম টি সল্ভ করব। আমরা এখানে DSU - DISJOINT SET UNION ডাটা স্ট্রাকচারের মাধ্যামে প্রব্লেম টি সল্ভ করব। DSU এর মাদ্ধ্যমে কোন একটি নোড কোন কম্পোনেন্টে বিলং করে তা ইজিলি বের করা যায়। সেইসাথে কোন একটি নোড কে একটি কম্পোনেন্টে কানেক্টেড করে দেয়া যায়। আমরা প্রথমে একটি ফাংশনের মাধ্যমে নোড গুলোকে কানেক্টেড করব। এরপর কানেক্টেড কম্পোনেন্টের প্রত্যক্টি কম্পেনেন্টের এজের ডিগ্রী চ্যাক করব। যদি সবগুলো কম্পোনেন্টের ডিগ্রী ২ হয় তাহলে কম...
