Cycle Detection in Graph — அடிப்படை

Cycle Detection in Graph — வரைபடத்தில் முக்கியமான நுட்பம்.

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

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

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

UF கட்டும்போது; DFS மூன்று நிறம்.

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))

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

• தந்தை விளிம்பு தவறு.

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

• topo தோல்வி=சுழற்சி.