DFS(爆栈)

(暴力枚举) $O(n^2)$

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

BFS

def bfs(i, c):    # AC
    import queue
    q = queue.Queue()

    colors[i] = c
    q.put((i, c))

    while not q.empty():
        t, c = q.get()
        if t not in g: continue
        for j in g[t]:
            if colors[j]==0:
                q.put((j, 3-c))
                colors[j] = 3-c
            elif colors[j]==c:
                return False
    return True

if __name__=="__main__":
    n, m = map(int, input().split())
    colors = [0]*(n+1)

    g = {}
    for i in range(m):
        u, v = map(int, input().split())
        if u not in g:
            g[u] = [v]
        else:
            g[u].append(v)
        if v not in g:
            g[v] = [u]
        else:
            g[v].append(u)

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