পাইথনে বিকল্প রং সহ সংক্ষিপ্ত পথ

ধরুন আমরা 0, 1, ..., n-1 লেবেলযুক্ত নোড সহ গ্রাফ নির্দেশিত করেছি। এই গ্রাফে, প্রতিটি প্রান্ত লাল বা নীল রঙে রঙিন, এবং সেখানে স্ব-প্রান্ত বা সমান্তরাল প্রান্ত থাকতে পারে। red_edges-এ প্রতিটি [i, j] নোড i থেকে নোড j পর্যন্ত একটি লাল নির্দেশিত প্রান্ত নির্দেশ করে। একইভাবে, blue_edges-এ প্রতিটি [i, j] নোড i থেকে নোড j পর্যন্ত একটি নীল নির্দেশিত প্রান্ত নির্দেশ করে। আমাদের দৈর্ঘ্য n এর একটি অ্যারে উত্তর খুঁজে বের করতে হবে, যেখানে প্রতিটি উত্তর [X] নোড 0 থেকে নোড X পর্যন্ত সংক্ষিপ্ততম পথের দৈর্ঘ্য যাতে প্রান্তের রঙগুলি পাথ বরাবর বিকল্প হয় (অথবা -1 যদি এমন পথ না থাকে বিদ্যমান)।

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

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

• bfs() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এতে re, be, f এবং n

  লাগবে

• পরিদর্শন নামে একটি সেট সংজ্ঞায়িত করুন, একটি সারি সংজ্ঞায়িত করুন এবং একটি ট্রিপলেট সন্নিবেশ করুন [0, f, 0]

• যখন q খালি নয়

  • ট্রিপলেট কারেন্ট, রঙ, q[0] হিসাবে ধাপ সেট করুন এবং q

    থেকে মুছুন

  • রঙ :=রঙের মান পরিপূরক (সত্য থেকে মিথ্যা এবং বিপরীতে)

  • res[বর্তমান] :=ন্যূনতম res [বর্তমান] এবং ধাপ

  • যদি রঙ অ-শূন্য হয়, তাহলে

    • প্রতিটি i re[বর্তমান]

      এর জন্য

      • যদি জোড়া (i, color) পরিদর্শনে না থাকে, তাহলে পরিদর্শনে (i, রঙ) প্রবেশ করান এবং q-তে [i, color, step + 1] ঢোকান

  • অন্যথায় যখন রঙ 0 হয়, তখন

    • প্রত্যেকের জন্য আমি [বর্তমান]

      • যদি জোড়া (i, color) পরিদর্শনে না থাকে, তাহলে পরিদর্শনে (i, রঙ) প্রবেশ করান এবং q-তে [i, color, step + 1] ঢোকান

• প্রধান পদ্ধতিতে -

• res :=অসীম মানগুলির একটি অ্যারে এবং এর আকার হল n

• re এবং be :=n খালি অ্যারের অ্যারে

• প্রতিটি এলিমেন্টের জন্য i r:insert i[1] in re[i[0]]

• প্রতিটি উপাদানের জন্য b-তে i:সন্নিবেশ করান i[1] be[i[0]]

  -এ

• কল bfs(re, be, false, n) এবং bfs (re, be, true, n) কল করুন

• 0 থেকে রেজ-এর দৈর্ঘ্য - 1

  রেঞ্জের জন্য i

  • যদি res[i] =inf, তাহলে res[i] :=-1

• রিটার্ন রিটার্ন

উদাহরণ(পাইথন)

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

class Solution(object):
   def shortestAlternatingPaths(self, n, r, b):
      self.res = [float("inf")] * n
      re = [[] for i in range(n) ]
      be = [[] for i in range(n) ]
      for i in r:
         re[i[0]].append(i[1])
      for i in b:
         be[i[0]].append(i[1])
      self.bfs(re,be,False,n)
      self.bfs(re,be,True,n)
      for i in range(len(self.res)):
         if self.res[i] == float('inf'):
            self.res[i]=-1
      return self.res
   def bfs(self,re,be,f,n):
      visited = set()
      queue = [[0,f,0]]
      while queue:
         current,color,step = queue[0]
         queue.pop(0)
         color = not color
         self.res[current] = min(self.res[current],step)
         if color:
            for i in re[current]:
               if (i,color) not in visited:
                  visited.add((i,color))
                  queue.append([i,color,step+1])
         elif not color:
            for i in be[current]:
               if (i,color) not in visited:
                  visited.add((i,color))
                  queue.append([i,color,step+1])
ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], []))

ইনপুট

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

আউটপুট

[0,1,-1]