পাইথনে যেকোনো সিটি থেকে যেকোনো সিটিতে যাওয়া সম্ভব কিনা যাচাই করার প্রোগ্রাম

মনে করুন nটি সিটি আছে ০ থেকে n-1 পর্যন্ত এবং roads একটি একমুখী রোডের তালিকা যা একটি সিটিকে অন্য সিটির সাথে সংযুক্ত করে। যেকোনো সিটি থেকে যেকোনো সিটিতে যাওয়া সম্ভব কিনা যাচাই করতে হবে।

উদাহরণস্বরূপ, n=3, roads=[[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]] হলে আউটপুট True।

সমাধানের ধাপসমূহ

• dfs(i, visited, g) ফাংশন সংজ্ঞায়িত করুন
  • i কে visited চিহ্নিত করুন
  • প্রতিটি j g[i]-এ, যদি visited নয়, dfs(j, visited, g)
• travel(g) ফাংশন সংজ্ঞায়িত করুন
  • visited := নতুন সেট, dfs(0, visited, g)
  • True ফেরত দিন যদি visited আকার == n
• মূল মেথড থেকে:
  • graph এবং rev_graph তৈরি করুন roads থেকে
  • True ফেরত দিন যদি travel(graph) এবং travel(rev_graph) উভয়ই True হয়

উদাহরণ

class Solution:
    def solve(self, n, roads):
        from collections import defaultdict
        graph = defaultdict(list)
        rev_graph = defaultdict(list)
        for u, v in roads:
            graph[u].append(v)
            rev_graph[v].append(u)
        def dfs(i, visited, g):
            visited.add(i)
            for j in g[i]:
                if j not in visited:
                    dfs(j, visited,g)
        def travel(g):
            visited = set()
            dfs(0, visited, g)
            return len(visited)==n
        return travel(graph) and travel(rev_graph)

ob = Solution()
n = 3
roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]
print(ob.solve(n, roads))

ইনপুট

3, [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]

আউটপুট

True