মান ল করুন একটি n সংখ্যা এবং enemies নামের একটি ২D ম্যাট্রিক্স। এখানে n নির্দেশ করে n জন ব্যক্তি যাদের লেবেল [0, n-1]। enemies-এ প্রতিটি সারি [a, b] ধারণ করে যার মানে a এবং b পরস্পর শত্রু। আমাদের পরীক্ষা করতে হবে কি n জন ব্যক্তিকে দুটি গ্রুপে ভাগ করা যায় যাতে কোনো দুজন শত্রু একই গ্রুপে না থাকে।
যদি ইনপুট হয় n = 4, enemies = [[0, 3],[3, 2]], তবে আউটপুট হবে True, কারণ আমরা [0, 1, 2] এবং [3] নামে দুটি গ্রুপ বানাতে পারি।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
graph := একটি খালি এডজেসেন্সি লিস্ট।
enemies-এ থাকা প্রতিটি (u, v) জোড়ার জন্য:
v কে graph[u]-এ যোগ করুন।
u কে graph[v]-এ যোগ করুন।
color := একটি নতুন ম্যাপ।
একটি dfs() ফাংশন সংজ্ঞায়িত করুন। এটি u, c := 0 গ্রহণ করবে।
যদি u color-এ থাকে, তবে color[u] == c হলে true ফেরত দিন।
color[u] := c
graph[u]-এ থাকা প্রতিটি v-এর জন্য dfs(v, c XOR 1) সব true হলে true ফেরত দিন।
মূল মেথড থেকে: ০ থেকে n-১ পর্যন্ত যেসব u color-এ নেই, তাদের dfs(u) সব true হলে true ফেরত দিন।
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class Solution: def solve(self, n, enemies): from collections import defaultdict graph = defaultdict(list) for u, v in enemies: graph[u].append(v) graph[v].append(u) color = {} def dfs(u, c=0): if u in color: return color[u] == c color[u] = c return all(dfs(v, c ^ 1) for v in graph[u]) return all(dfs(u) for u in range(n) if u not in color) ob = Solution() n = 4 enemies = [[0, 3],[3, 2]] print(ob.solve(n, enemies))ইনপুট
4, [[0, 3],[3, 2]]
আউটপুট
True
