মডিউল ৯_২ঃ Find if Path Exists in Graph [Leetcode]

এই প্রব্লেমে আপনাকে একটি গ্রাফের Number of Nodes (n), edges , source and destination দিয়ে দেয়া হবে। আপনার থেকে বের করতে হবে source থেকে destination এ যাওয়া সম্ভব কিনা।

Example 1:

source = 0 and destination = 2 গ্রাফ দেখে বুঝা যাচ্ছে 0 নোড থেকে 2 নোডে যাওয়া সম্ভব, তাই এইটির জন্য true return করতে হবে।

Example 2:

source = 0 and destination = 5 গ্রাফ দেখে বুঝা যাচ্ছে 0 নোড থেকে 5 নোডে যাওয়া সম্ভব নয়, তাই এইটির জন্য false return করতে হবে।

সমাধান

memset(vis, false, sizeof(vis));
for (int i = 0; i < edges.size(); i++)
{
    int a = edges[i][0];
    int b = edges[i][1];
    v[a].push_back(b);
    v[b].push_back(a);
}
dfs(source);

vis array তে false assign করেছি। এরপর Adjacency matrix কে Adjacency list এ convert করেছি। dfs function call করেছি source দিয়ে।

void dfs(int s)
{
    vis[s] = true;
    for (int child : v[s])
    {
        if (!vis[child])
        {
            dfs(child);
        }
    }
}

dfs function এর শুরুতে source কে ভিজিটেড করেছি, এরপর source এর child নোড বের করেছি, যদি child node টি আনভিজিটেড হয় তাহলে সেই child কে dfs function কে recursive কল করেছি। এইভাবে source থেকে dfs চালানো পর , vis array তে চেক করবো destination ভিজিটেড হয়েছে কিনা। যদি destination node ভিজিটেড হয়ে থাকে তাহলে আমরা true return করবো কারণ source থেকে destination এ যাওয়া সম্ভব, অন্যথায় false return করবো।

সম্পূর্ণ কোড

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> v[200005];
    bool vis[200005];
    void dfs(int s)
    {
        vis[s] = true;
        for (int child : v[s])
        {
            if (!vis[child])
            {
                dfs(child);
            }
        }
    }
    bool validPath(int n, vector<vector<int>> &edges, int source, int d)
    {
        memset(vis, false, sizeof(vis));
        for (int i = 0; i < edges.size(); i++)
        {
            int a = edges[i][0];
            int b = edges[i][1];
            v[a].push_back(b);
            v[b].push_back(a);
        }
        dfs(source);
        return vis[d];
    }
};