DFS Tree Preprocessing — அடிப்படை

DFS Tree Preprocessing — வரைபடத்தில் முக்கியமான நுட்பம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

வரைபடம், சமூக வலை, சார்பு அமைப்பு — தலைகோடுகள்/விளிம்புகள் மாதிரி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

சுயமுறை/அடுக்கு; visited; மரத்தில் தந்தை.

Pythonில் முயற்சி செய்வோம்

def dfs(adj: list[list[int]], start: int) -> list[int]:
    seen = set()
    order: list[int] = []

    def go(u: int) -> None:
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                go(v)

    go(start)
    return order


print(dfs([[1, 2], [0], [0]], 0))

பொதுவான தவறுகள்

• ஆழம் அதிகம்.
• visited இழப்பு.

முக்கிய பாடங்கள்

• மூன்று நிற சுழற்சி.
• நேர முத்திரை.