Strongly Connected Components — அடிப்படை

Strongly Connected Components — வரைபடத்தில் முக்கியமான நுட்பம்.

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

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

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

சுருக்கு வரைபடம்; low-link.

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

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

• திசை vs திசையற்ற குழப்பம்.

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

• 2-SAT SCC.
• Kosaraju பின் Tarjan.