python解决已知点和线，求根据点和线组成的图形分组问题。

Question

如下数据结构：输入已知点（nodes）,线（lines）：

{
        "nodes": ["A", "B", "C","D","F"],
        "lines": [["A", "B"], ["C", "A"],["D","F"]]
    }

需对现有点和线组成的图形进行分组，输出如下：

"result": {"group": {"A": "#1", "C": "#1", "B": "#1", "D": "#2", "F": "#2"}, "pile": {"#2": ["D", "F"], "#1": ["A", "C", "B"]}}

请教按照上述例子用python写一个函数，感激不尽。

Answer 1

def f(nodes, lines):
    d = {i: 0 for i in nodes}
    g = {i: [] for i in nodes}
    for i in lines:
        d[i[0]] += 1
        d[i[1]] += 1
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    group = {}
    l = 0
    while d:
        m = min(d.items(), key=lambda x: x[1])
        d.pop(m[0])
        if m[0] not in group and not (set(g[m[0]]) & set(group)):
            l += 1
        group[m[0]] = f'#{l}'
        for i in g[m[0]]:
            if i in d:
                d[i] -= m[1]
                group[i] = group[m[0]]
                if d[i] == 0:
                    d.pop(i)
    pile = {f'#{i + 1}':[] for i in range(l)}
    for k, v in group.items():
        pile[v].append(k)
    return group, pile


print(f(**{'nodes': ['A', 'B', 'C', 'D', 'F'], 'lines': [['A', 'B'], ['C', 'A'], ['D', 'F']]}))