1049 - One Way Roads

1049 - One Way Roads

Topic: DFS

concept: কস্টকে ডিরেক্টটেড ধরবো তারপর আনডিক্টটেড গ্রাফ এ ডিএফএস চালাবো.

Share:

Read More

TOPOSORT - Topological Sorting

TOPOSORT - Topological Sorting

Topic: Topological Sorting

Share:

Read More

Topological Sorting

                                                 Resource Link

Topological Sorting (E-Maxx)

Kahn’s algorithm for Topological Sorting

Topological Sorting

TopSort using DFS:

TopSort using BFS: (Kahn’s algorithm)

Share:

Read More

F1. Tree Cutting (Easy Version

F1. Tree Cutting (Easy Version)

Topic: DFS

Concept: প্রতিটা প্যারেন্ট এর চাইল্ড কোন কোন কালার আছে তার হিসাব রাখবো, যেমন প্রথম উদাহরনে -

১ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল, ২টা নীল , ১টা নরমাল।

২ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল, ১টা নীল , ২টা নরমাল।

৩ নং এর ১টা নরমাল (নিজের কালার)।

৪ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল ( এইটা বাদ দিয়ে এন্সার পাব)।

৫ নং নোডের চাইল্ড এর সংখ্যা হবে 1টা নীল।

Solution 01:

Share:

Read More

802. Find Eventual Safe States

802. Find Eventual Safe States

 

Solution: DFS

concept:

যেই নোডগুলোতে সাইকেল নাই ওই গুলা প্রিন্ট করতে হবে।

Code:

class Solution {
public:
   
    unordered_set<int> cycle_nodes, safe_nodes;
   
    bool dfs(vector<vector<int>>& g, int i, unordered_set<int>visited_nodes)
    {
        if(safe_nodes.find(i) != safe_nodes.end())return true;
        if(cycle_nodes.find(i) != cycle_nodes.end())return false;
       
        if(visited_nodes.find(i) != visited_nodes.end()){
            cycle_nodes.insert(i);
            return false;
        }
       
        visited_nodes.insert(i);
        for(int node : g[i]){
            if(!dfs(g, node, visited_nodes)){
                cycle_nodes.insert(i);
                return false;
            }
        }
        safe_nodes.insert(i);
        return true;
    }
   
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        unordered_set<int>visited_nodes;
        vector<int>ans;
       
        for(int i = 0; i < graph.size(); i++){
            if(dfs(graph, i,visited_nodes))ans.push_back(i);
        }
        return ans;
    }
};

Share:

Read More