Checkio笔记 —— node-subnetworks

一鼓作气把接下来一道题也完成了，记录一下。

题目

这道题关于网络的定义和前面那一道类似，只是当故障发生的时候，需要计算这些没有发生故障的网络节点，被分成了多少个分网络。如下面这张图所示，当B发生故障时，C-D连在一起是一个分网络，A独自称为一个分网络。
所以，和前面那道题类似，采用如下的方式来表示这个网络及故障情况：

• 网络的连接情况表示为：[['A','B'],['B','C'],['C','D']]

• 故障发生节点用列表表示：A点发生故障为['A']，AB同时发生故障为['A','B']

  
  通信网络

代码思路

• 剔除发生故障的网络节点，将正常工作的网络节点放在一个列表中
• 剔除发生故障的网络连接，将正常的网络连接保存在一个列表中
• 定义一个递归函数，可以从任意一个正常网络节点开始，寻找能和该点连接的所有网络节点，寻找完毕则计数一个子网络。并将该子网络中的所有网络节点删除。
• 继续寻找子网络并计数，直到没有节点剩余

我的代码如下：

def subnetworks(net, crushes):
    nodes = [] 
    for i in net:
        for j in i:
           nodes.append(j)
    node_name = list(set(nodes))
      
    #去掉故障节点
    for node in crushes:
        node_name.remove(node)
    
    #故障后网络中剩余的网络链接数，记录在net列表中
    for connect in net:
        for crush in crushes:
            if crush in connect:
                net.remove(connect)

    #该函数可以确定那些节点是联系在一起的
    def connect_node(sours,net,targ):
        org_targ = targ[:]
        for node in org_targ:
            if [sours,node] in net or [node,sours] in net:
                targ.remove(node)
                connect_node(node, net, targ)
                    
    count = 0
    while len(node_name) >= 1:
        for source in node_name:
            node_name.remove(source)
            connect_node(source, net, node_name)
            count += 1
    return count

if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert subnetworks([
            ['A', 'B'],
            ['B', 'C'],
            ['C', 'D']
        ], ['B']) == 2, "First"
    assert subnetworks([
            ['A', 'B'],
            ['A', 'C'],
            ['A', 'D'],
            ['D', 'F']
        ], ['A']) == 3, "Second"
    assert subnetworks([
            ['A', 'B'],
            ['B', 'C'],
            ['C', 'D']
        ], ['C', 'D']) == 1, "Third"
    print('Done! Check button is waiting for you!')

其他人的代码

代码一

def subnetworks(net, crushes):
    connected = []
    for i in net:
        if i[0] not in crushes and i[0] not in connected:
            connected += i[0]
        if i[1] not in crushes and i[1] not in connected:
            connected += i[1]
    
    c = len(connected)
    for i in net:
        if i[0] in connected and i[1] in connected:
            c -= 1
    
    return c

代码二

def subnetworks(net, crushes):
    nodes = set(sum(net, [])) - set(crushes)
    subcount = 0
    while nodes:
        subcount += 1
        stack = [nodes.pop()]
        while stack:
            node = stack.pop()
            for conn in net:
                if node == conn[0] and conn[1] in nodes:
                    stack.append(conn[1])
                    nodes.remove(conn[1])
                if node == conn[1] and conn[0] in nodes:
                    stack.append(conn[0])
                    nodes.remove(conn[0])
    return subcount