(DFS) $O(n+m)$

Python 代码

DFS 版 爆栈stack

def dfs(i,c): 
    colors[i] = c
    if i not in graph:return False
    for j in graph[i]:
        if colors[j]==0:
            if dfs(j, 3-c)==False:
                return False
        elif colors[j]==c:
            return False
    return True
if __name__=="__main__":
    n, m = map(int, input().split())
    colors = [0 for i in range(n+1)]
    graph = {}
    # 处理重边和自环了
    while m:    
        u, v = map(int, input().split())
        if u==v:
            m-=1
            continue
        if u not in graph:
            graph[u] = [v]
        else:
            graph[u].append(v)
        if v not in graph:
            graph[v] = [u]
        else:
            graph[v].append(u)
        m-=1

    for i in range(1,n+1):
        if colors[i]==0:
            res = bfs(i, 1)
            if res==False:
                break
    print("Yes") if res else print("No")

来自Actor，我单独再发一遍自己收藏