Bipartite Graph Checking

গ্রাফ থিওরি শিখতে গেলেই অনেক আমাদের ধরনের গ্রাফের সাথে পরিচয় হয়ে উঠে, এর মধ্যে বাইপারটাইট গ্রাফ অন্যতম।

এইখানে আমারা গ্রাফের সব নোড গুলাকে দুইটা সেটে বিভক্ত করে ফেলি। এমনভাবে বিভক্ত করি যেনো একই সেটের নোডের মধ্যে কোনো Edge/Vertices না থাকে অর্থাৎ একটা সেটের নোড শুধুমাত্র অন্য আরেকটা সেটের নোডের সাথে কানেক্টেড থাকে।

পাশের চিত্রে খুব সুন্দরভাবে একটা বাইপারটাইট গ্রাফকে দেখানো হইছে। দুইটা সেট U and V তে ভাগ করা হইছে, এবং একই সেটের নোডের মধ্যে কোনো কানেক্টিভিটি নাই।

কোডিং এর ক্ষেত্রেও জিনিস টা সেইম ভাবে চিন্তা করা যায় । আমরা দুইটা সেইটে বিভক্ত না করে, দুইটা কালার দিয়ে রিপ্রেজেন্ট করবো 0 and 1.

DFS মাধ্যমে খুব সহজেই বাইপারটাইট চেইক করা যায়। একটা Visited Array এবং একটা Color Array র মাধ্যমে পুরো প্রসেস টা শেষ হবে। আমরা Boolean Types এর DFS ব্যবহার করবো 

প্রথমে আমরা কালার ১ দিয়ে প্রথম নোড এর DFS চালাবো, এই নোড কে ভিসিটেড এবং কালার এরেতে আপডেট করার পরে, এর এডজেসেন্সি লিস্টে গিয়ে দুইটা জিনিস চেইক করবো 

১। ঐ নোডের চাইল্ডগুলাকে ডিফ্রেন্ট কালার দিয়ে DFS চালালাইলে True/False কি রিটার্ন করে
২। ঐ নোড এবং চাইল্ড সেইম কালার কিনা, সেইম হইলে False

পরিশেষে DFS  True রিটার্ন করবে, কারন এর আগে আমাদের দুইটা কেইস চেইক করার পরেও বাইপারটাইট পাইনাই।

Easy Implementation

Related Problems:
Graph Without Long Directed Paths
BUGLIFE - A Bug’s Life

Cycle Detection In a Graph

কম্পিটিটিভ প্রোগ্রামিংয়ে আমরা সাধারনত দুই ধরনের গ্রাফ নিয়ে কাজ করে থাকি(আরও অনেক ধরনের গ্রাফ আছে)। ডিরেক্টেড গ্রাফ এবং আনডিরেক্টেড গ্রাফ।
সাধারনত যে সব গ্রাফের দিক নির্দেশক থাকে অর্থাৎ এক নোড থেকে এক্সাক্টলি কোন কোন কোন নোডে যাওয়া যাবে তার দিকে নির্দেশক থাকে সেই গুলাকে ডিরেক্টেড গ্রাফ বলে, অন্যদিকে যে গুলাতে নির্দেশক থাকে না ঐগুলা কে আনডিরেক্টেড গ্রাফ বলে।

গ্রাফের একটা নোড থেকে ভিসিট করা শুরু করলে যদি কোনো একটা টাইমে ঐ নোডেই ফিরে আসা যায় তাহলে বুঝতে হবে এটা একটা সাইকেল।
পাশের ছবিতে দুইটা গ্রাফ আছে , একটা ডিরেক্টেড এবং আরেকটা আনডিরেক্টেড।
ডিরেক্টেড গ্রাফের ১,২ এবং ৩ নাম্বার নোড একটা সাইকেল তৈরি করে।
অন্যদিকে আনডিরেক্টেড গ্রাফের ১,২,৩ এবং ২,৩,৪ দুইটা সাইকেল তৈরি করে।

আমরা এই সাইকেল খোজা কাজটা প্রোগ্রামিং এর মাধ্যমে কিভাবে করতে পারি এবং সাইকেল টাও যেনো প্রিন্ট করতে পারি, এটাই আজকের আলোচ্য বিষয়। All nodes are 0 based.

সাইকেল খুজতে যা যা জানা থাকলে দ্রুত বুঝতে সুবিধা হবেঃ
১ঃ যেকোনো প্রোগ্রামিং ল্যাংগুয়েজ দিয়ে কিভাবে গ্রাফ এর কাজ(ইনপুট/আউটপুট/ট্রাভার্স) করে। 

২ঃ রিকার্সন

ডিরেক্টেড গ্রাফে সাইকেল খোজা

প্রথমে আমরা তিনটা বক্সের সাথে পরিচত হয়ে নিই।
১। সাদা বক্স - শূন্য দ্বারা রিপ্রেজেন্ট করবো (নোড এখোনো ভিজিট হইনাই)
২। ধুসর বক্স - এক দ্বারা রিপ্রেজেন্ট করবো (নোড ভিজিটেড)
৩। কালো বক্স - দুই দ্বারা রিপ্রেজেন্ট করবো (নোডের সব চাইল্ড ভিজিটেড)
একটা Color Array দিয়ে বক্সের কাজ করবো।

একই সাথে সাইকেল এর শুরু এবং শেষ বুঝতে দুইটা ভেরিয়েবল নিবো এবং প্রত্যেকটা নোড এর প্যারেন্ট নোড মার্ক করে রাখতে একটা Array নিবো, যাতে আমাদের সাইকেল প্রিন্ট করতে সুবিধা হয়।

যেহুতু আমরা রিকার্সন জানি, তারমানে আমরা DFS ও জানি, DFS হচ্ছে একটা গ্রাফ Traversing Algorithm. এখানে আমাদের DFS Function টা হবে বুলিয়ান টাইপ্স।

এইগুলা দিয়ে কয়েকটা স্টেপে ডিরেক্টেড গ্রাফে সাইকেল খোজা সম্ভব
১। প্রথমে সব গুলা নোডকে শূন্য(0) দ্বারা মার্ক করে নিবো অর্থাৎ সাদা বক্সে রেখে দিবো, সবগুলা নোডের প্যারেন্ট -1 করে দিবো, Cycle_Start ভ্যারিয়েবল -1 করে রাখবো অর্থাৎ DFS শেষ হবার পরেও Cycle_Start = -1 থাকা মানে কোনো সাইকেল পাইনি।

২। একটা নোড যখন DFS এ ঢুকবে তখন সেটাকে ১ দ্বারা মার্ক করবো অর্থাৎ ধুসর বক্সে রাখবো।
৩। ঐ নোড এর Adjacent অর্থাৎ চাইল্ড নোড গুলা ভিজিট করা শুরু করবো, একটা লুপ দিয়েই করা যায়।
এইখানে দুইটা কেইস হইতে পারে,
-> যদি ঐ নোডের চাইল্ড এখনো সাদা বক্সেই থাকে অর্থাৎ এখনো তাকে ভিজিট না করা হয়ে থাকে তাহলে আমরা সেই চাইল্ডের প্যারেন্ট অর্থাৎ বর্তমান নোডকে মার্ক করবো। সাথে সাথে ঐ চাইল্ড দিয়ে আবার DFS চালাবো একইসাথে দেখবো সে True রিটার্ন করে কিনা।
-> যদি ঐ নোডের চাইল্ড কে আমরা অলরেডি ধুসর বক্সে দেখি অর্থাৎ সে ভিজিটেড(১ দ্বারা মার্ক) থাকে তাহলে বুঝতে হবে এখানে সাইকেল আছে।
যার শুরু ঐ নোড থেকে এবং শেষ ঐ নোডের চাইল্ডে, এটা মার্ক করার জন্য অলরেডি আমরা দুইটা ভ্যারিয়েবল ডিক্লেয়ার করে রাখছি।

৪। ঐ নোডের Adjacent অর্থাৎ সব চাইল্ড ভিজিট করা শেষ হয়ে গেলে আমরা তাকে কালো বক্সে অর্থাৎ ২ দ্বারা মার্ক করে রাখবো, একই সাথে False return করবো। কারন আপাতত আমরা কোনো সাইকেল পাইনি।

Easy Implementation



আনডিরেক্টেড গ্রাফে সাইকেল খোজা

আমরা জানি আনডিরেক্টেড গ্রাফে কোনও দিক নির্দেশক থাকে না অর্থাৎ যেকোনো নোড থেকে বাকি যেকোনো নোডে যাওয়া যাবে। 
এইখানে সাইকেল খোজার জন্য আমাদেরকে কালারিং করার কোনো দরকার নাই কারন যে নোডে আমরা একবার ভিজিট করবো তার চাইল্ড একবার ই ভিজিট  হবে, এর বেশি হবে না। 
সুতরাং আমরা এখানে একটা Visited Array ব্যবহার করবো।

এখানেও কয়েকটা ধাপে আমরা সাইকেল সাইকেল পাইতে পারি।

১। প্রথমে সব গুলা নোড আনভিজিটেড অর্থাৎ Initially False করে রাখবো, সব গুলা নোডের Parent -1 করে রাখবো ।

২। Traversing এর শুরুতে অর্থাৎ নোড যখন DFS এ ঢুকবে তখন ভিজিটিড (True) করে দিবো।

৩। ঐ নোডের চাইল্ড নোড গুলা Traverse করবো, একটা লুপ চালিয়েই করা যাবে, চাইল্ড যদি তার প্যারেন্টের এর সমান হয় তাহলে ঐ চাইল্ড কে ইগ্নোর করবো।

চাইল্ড ভিজিটিং এর ক্ষেত্রে দুইটা কেইস হইতে পারে,

->  যদি চাইল্ড নোড ভিজিটেড থাকে তাহলে আমরা এখানে সাইকেল পাবো,একই ভাবে আগের মত সাইকেলের শুরু এবং শেষ মার্ক করবো। একই সাথে True Return করে দিবো।

এর পর চাইল্ড এর Parent নোড আপডেট করবো।

-> চাইল্ড কে তার প্যারেন্ট নোড দিয়ে আবার DFS এ চেইক করবো True Return করে কিনা।
৩। সব শেষে False Return করবো।

Easy Implementation



ডিরেক্টেড এবং আনডিরেক্টেড গ্রাফের সাইকেল প্রিন্টিং

ডিরেক্টেড এবং আনডিরেক্টেড দুই ক্ষেত্রেই সাইকেল প্রিন্টিং এর কাজ টা সেইম।

আমরা দুই ক্ষেত্রেই প্রত্যেকটা Node এর Parent মার্ক করে রাখছি একই সাথে সাইকেলে র শুরু এবং শেষ মার্ক করে রাখছি।

এখন, একটা লুপের মাধ্যমেই আমরা পুরো সাইকেল টা খুজে পাইতে পারি। প্রথমে একটা Cycle Array রাখবো সাইকেলের নোড গুলা প্রিন্ট স্টোর করার জন্য।

        for(int v = cycle_end; v != cycle_start; v = parent[v]){

            cycle.push_back(v);

        }
এখানে সাইকেলের শেষ থেকে লুপ শুরু হইছে, যতক্ষন না সাইকেলে র শুরু তে না পৌছায় ততক্ষন লুপ চলতে থাকবে । প্রত্যেকবার ঐ নোডের প্যারেন্ট দ্বারা লুপ আপডেট করবো।

জিনিসটা আরো সুন্দর ভাবে বোঝা যেতে পারে, ধরি আমরা একটা নোড v তে আছি, এর প্যারেন্ট নোড এর প্যারেন্ট নোডে যাইতে v কে , V এর প্যারেন্ট দ্বারা আপডেট করবো।

Easy Implementation



Full Cycle Detection Implementation



Related Problems:

Round Trip
Round Trip II
Find Eventual Safe States (find nodes that are not in a cycle)
Cyclic Components

Diameter of a Tree

The diameter of a tree is the longest path between any two nodes of a given tree.

For a better understanding look at the picture, here the diameter is 6, why? Because if we take two nodes, '8' and '9' the distance will be maximum. There are no pairs whose distance is greater than (8,9) pair. So diameter is 6 in this case. See, we are considering edges, not vertices.

So, how can we calculate the diameter of a tree! Basically, we can solve it using BFS or DFS. Let's discuss it one by one.

Using DFS,

Suppose there are N nodes, every time we will take any nodes and run a dfs from this node(Assume chosen node is root), at the same time we will update maximum distance. 
In this case, the runtime will be O(n^2), n nodes, and every time a dfs.

So this is huge, can we optimize it? 
Yes, we can optimize it by using two(2) DFS.

First, we choose a root node ( say 1 ), we start our first dfs from the root node, suppose we got the deepest node is 'X'.
Second, we start another dfs from node 'X', and finally, we can get our desired answer( maximum distance aka diameter ).

Using BFS,
Same as before we did in dfs, again we will find any longest node Using First BFS and after that, we will start another BFS from this node. In BFS, Implementation is slightly different.

Related problems:

1. Tree Diameter - CSES 
2. PT07Z - Longest path in a tree-Spoj 
3. LOJ-1094
4. Diameter of a tree-Leetcode

For better understanding see the code given below,

Making A Large Island

Problem:

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in the grid after applying this operation. An island is a 4-directionally connected group of 1s.

Example,

Input: grid = [[1,0],[0,1]]

Output: 3

Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Approach:

First, let's try to understand the problem. After changing at most one 0 to 1, we have to return the maximum size of a connected component. This connected component is made by only 1. See, we can't count the element that is diagonally connected, we have to count them, those are only connected by 4-directionally.

let's illustrate an example.

Initially, we see here, a total of 3 connected components, and the max size is 3.

After changing one 0 to 1, we found the maximum size of connected components means the biggest Island size is 6.

Now come to the main point, how can we count these connected components and their sizes? Basically, we don't need how many connected components are there, we just need their sizes.

Now, How can we store every connected component's size. See we can mark every component by a specific name.

Suppose first Connected Components elements are 2, then 3, then 4, and so on.

After that, we simply store it in the map by [key, value] pair, like this, mark[2] = 3. Means in 2 components size is 2.

I am trying to say that, we will replace every connected component one(1) with another unique id, like (2,3,4,...etc).

Let's illustrate what happened after changing all components id.

After changing all connected components element we see, have all are different now. Now, they have a unique id.

Using DFS we can do this, every time we will change the id, and count them up.

After changing their id, we can simply consider all zero, which means by brute-forcing(n*m)every time we will check how many id's can be found in 4-directionally.

Hence multiple id can be counted, so will use set, after that simply add their sizes with 1(0 changes to 1 now its included to island). For a better understanding check the code, And code by yourself, because you can't copy this, LOL :D

Introduction to DFS (Depth First Search)

Intro:

The Depth First Search known as DFS is an algorithm for traversing a graph or tree data structure. DFS traversing start from a root node. DFS tries to visit in-depth in all possible ways after that comes back to the root node, then goes to another depth, and so on.
Let's try to visualize the scenario.

Here, the red line shows us starting the traversing and the blue line shows after traversing it comes back to the root node, this is simply called backtracking.

The one possible traversing can be,

1-2-3-4-5-6-7-8-9-10

Also,

1-2-3-4-5-8-6-7-9-10 can be possible.

The Complexity of DFS traversing is O(v+E), V is the number of nodes, and E is the number of edges. This is really easy to understand.

I the near future we will discuss some DFS related problems, then it will be more clear.