প্রোগ্রাম চেক করার জন্য আমরা যে কোন শহর থেকে যে কোন শহরে যেতে পারি নাকি পাইথনে নেই

ধরুন আমাদের n শহরগুলিকে পরিসরে একটি সংখ্যা হিসাবে উপস্থাপন করা হয়েছে [0, n) এবং আমাদের কাছে একমুখী রাস্তার একটি তালিকাও রয়েছে যা এক শহরকে অন্য শহরকে সংযুক্ত করে। আমরা কোন শহর থেকে কোন শহরে পৌঁছাতে পারি কিনা তা পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুটটি n =3 এর মত হয়, রাস্তা =[[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]] , তাহলে আউটপুট হবে True, যেমন আপনি যেতে পারেন 0 থেকে 1 এবং 1 থেকে 0

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব−

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এর জন্য i, পরিদর্শন করা, g

  লাগবে

• আমি পরিদর্শন হিসাবে চিহ্নিত করুন

• g[i]-এ প্রতিটি j-এর জন্য, do

  • যদি j পরিদর্শন না করা হয়, তাহলে

    • dfs(j, পরিদর্শন করা, g)

• একটি ফাংশন ভ্রমণ () সংজ্ঞায়িত করুন। এটি g

  লাগবে

• পরিদর্শন করেছেন :=একটি নতুন সেট

• dfs(0, পরিদর্শন করা, g)

• পরিদর্শনের আকার n

  এর মতো হলে সত্য ফেরত দিন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন−

• গ্রাফ :=একটি খালি মানচিত্র

• rev_graph :=একটি খালি মানচিত্র

• প্রতিটি উৎসের জন্য u, এবং গন্তব্য v রাস্তায়, do

  • গ্রাফ[u]

    -এর শেষে v সন্নিবেশ করান

  • rev_graph[v>

    এর শেষে u ঢোকান

• প্রত্যাবর্তন সত্য যখন ভ্রমণ(গ্রাফ) এবং ভ্রমণ(রেভ_গ্রাফ) উভয়ই সত্য হয়

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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