需要一些帮助正确地将BFS树排序成两个单独的订订者

Question

我有我试图获取所有内容的代码

from collections import deque

def bubbles(physical_contact_info):
    """takes physical contact info about a group of people and determines the bubbles."""
    result = []
    contacted = []
    non_contacted = []

    adj = adjacency_list(physical_contact_info)
    j = 0
    print(j)
    print(adj)
    for x in range(len(adj)-1, -1, -1):
        info = dfs_tree(adj, j)
        print(info)
        i = len(info)-1
        while info[i] != None:
            contacted.insert(0, i)
            i = info[i]
            #print(i)
            #print(contacted)
        if info[i] == None:
            non_contacted.insert(0, i)
    
    if len(non_contacted) != 0:
        result.append(non_contacted)
    if len(contacted) != 0:
        result.append(contacted)
    return result
    
def adjacency_list(graph_str):
    """>"""
    splitted = graph_str.splitlines()


    header = splitted[0]
    number_of_vertices = int(header.split()[1])

    adjacent = [[] for vertex in range(number_of_vertices)]

    #check if weighted, directed
    if header[-1] == "W":
        is_weighted = True
    else:
        is_weighted = False
   
    if is_weighted:
        if header[0] == "D":
            for line in splitted[1:]:
                new_line = line.split()
                adjacent[int(new_line[0])].append((int(new_line[1]), int(new_line[2])))
        else:
            for line in splitted[1:]:
                new_line = line.split()
                adjacent[int(new_line[0])].append((int(new_line[1]), \
                int(new_line[2])))
                adjacent[int(new_line[1])].append((int(new_line[0]),\
                int(new_line[2])))


    else:
        if header[0] == "D":
            for line in splitted[1:]:
                new_line = line.split()
                adjacent[int(new_line[0])].append((int(new_line[1]), None))
        else:
            for line in splitted[1:]:
                new_line = line.split()
                adjacent[int(new_line[0])].append((int(new_line[1]), None))
                adjacent[int(new_line[1])].append((int(new_line[0]),None))
    return adjacent


def dfs_tree(adj_list, start):
    """."""
    number_of_vertices = len(adj_list)
    state = ["U" for i in range(number_of_vertices)]
    parent = [None for i in range(number_of_vertices)]
    state[start] = "D"
    new = dfs_loop(adj_list, start, state, parent)
    return parent


def dfs_loop(adj_list, u, state, parent):
    """."""
    for v, weight in adj_list[u]:
        if state[v] == "U":
            state[v] = "D"
            parent[v] = u
            dfs_loop(adj_list, v, state, parent)
    state[u] = "P"


physical_contact_info = """\
U 2
0 1
"""

print(sorted(sorted(bubble) for bubble in bubbles(physical_contact_info)))
#Should be returning [[0, 1]], currently getting [[0, 1], [1]]

，以便最终它将返回一个由两个sublists组成的列表，这是一个未连接到另一个的每个顶点之一（如果愿意的话，则是“无接触”），另一个包含每个顶点的列表确实与另一个连接（“联系”）。我很难将树的内容插入正确的列表中，因为我不知道该怎么做才能将这些顶点添加到正确的列表中。帮助您将不胜感激！

其他测试用例

案例1：

physical_contact_info = """  
U 2
"""

print(sorted(sorted(bubble) for bubble in bubbles(physical_contact_info)))

输出应为：

[[0]，[1]]

情况2：

physical_contact_info = """  
U 7
1 2
1 5
1 6
2 3
2 5
3 4
4 5
"""

print(sorted(sorted(bubble) for bubble in bubbles(physical_contact_info)))

输出应为：

[[0]，[1，2，3，4，5，6]]

案例3：

physical_contact_info = """  
U 0
"""

print(sorted(sorted(bubble) for bubble in bubbles(physical_contact_info)))

输出应为：

[]

情况4：

physical_contact_info = """  
U 1
"""

print(sorted(sorted(bubble) for bubble in bubbles(physical_contact_info)))

输出应为：

[[0]]

目前一直在考虑循环的，但仍然不确定是否有帮助或是否有必要。