大投入城市建设方案超时

Question

问题

哈克尔兰国家有n城市连接的m单向公路.这些城市从1到n都有编号。最近，政府决定在哈克尔兰建设新城市。您的任务是模拟q事件。事件可以有两种类型，如下所述：

• 1 x d：在Hackerland建造了一个新的城市n + 1，它与城市x相连。如果是d = 0，新路的方向是从x到n + 1。如果是d = 1，新路的方向是从n + 1到x。
• 2 x y：如果可以从城市x迁移到城市y，则打印No，否则打印D24。

约束

0< n，m <= 50000 0

您可以找到对问题这里的完整描述。

My努力

我试图在这里使用BFS，但是所有的测试用例都失败了，但是由于超时，默认的测试失败了。对于那些测试用例，n >= 4000. m >= 20000。

代码

from collections import defaultdict, deque

n, m = map(int, input().split())

adjacentNodes = defaultdict(set)
for _ in range(m):
    u, v = map(int, input().split())
    adjacentNodes[u].add(v)

q = int(input())
for _ in range(q):
    c, x, d = map(int, input().split())

    if c == 1:
        n += 1
        y = n

        if d == 0:
            adjacentNodes[x].add(y)
        else:
            adjacentNodes[y].add(x)
    else:
        y = d
        visited = set()
        current = deque()
        current.append(x)
        answer = "No"
        while current:
            parent = current.popleft()
            if parent == y:
                answer = "Yes"
                break
            if parent in adjacentNodes:    
                for i in adjacentNodes[parent]:
                    if i not in visited:
                        visited.add(i)
                        current.append(i)
        print (answer) 

问题

有没有人建议如何优化解决方案？

Answer 1

这是一个艰难的过程，但我设法解决了它，并通过了所有的测试用例。以下是要点。

首先Build一个完全有向图

保存查询，因为可以使用它们的100,000，并且首先构建一个完整的图，然后在上面运行所有的查询，效率更高。

Find所有强连接组件

在图中找到所有强连通的组件，然后基于它们构建一个可达映射。它具有较低的空间复杂度，因为每个强组件都可以由单个节点表示，因此我们不需要为每个节点设置一个可达性集，而只需要为其代表设置一个可达性集。

用于查找可达集的Use DFS

修改DFS，以便在运行DFS之后，每个连接组件都包含其他可访问的连接组件的代表(所谓的低链路节点)。但是，如果一个低链路节点是可访问的，那么来自其连接组件的任何节点也是可访问的。

有效存储强组件的Use内存

创建一个(n + 1)整数值数组，其中n -图中的节点数。索引标识图中的一个节点和一个值-所有连接的组件(低链路节点)可从图中到达。值可以有最多n + 1二进制数字(如果所有节点都可以从当前节点到达)。

<#>Increase递归限制

由于节点数可以到达50000，因此必须将递归调用堆栈设置为此值。

Solution代码

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(50001)

n, m = map(int, input().split())
adjacentNodes = defaultdict(set)
for _ in range(m):
    u, v = map(int, input().split())
    adjacentNodes[u].add(v)

q = int(input())
# read all queries first
queries = []
for i in range(q):
    c, x, d = map(int, input().split())
    if c == 1:
        n += 1
        y = n
        if d == 0:
            adjacentNodes[x].add(y)
        else:
            adjacentNodes[y].add(x)
    else:
        y = d
        queries.append((x, y))

# each node with number i corresponds to 2^i
nodeDpPosition = {i: (1 << i) for i in range(n + 1)}
# Implementation using the Tarjan algorithm
# https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
def findAllConnectedComponents(edges):
    connectedComponents = [0 for _ in range(n + 1)]
    index = {'value' : 0}
    # map node to its connected component low link node
    connectedComponentLink = {}

    nodeStack = deque()
    indices = [-1] * (n + 1)
    lowLinks = [0] * (n + 1)
    onStack = [False] * (n + 1)

    def connectedComponent(node):
        indices[node] = index['value']
        lowLinks[node] = index['value']
        index['value'] += 1
        nodeStack.append(node)
        onStack[node] = True

        for adjacentNode in edges[node]:
            if indices[adjacentNode] < 0:
                connectedComponent(adjacentNode)
                lowLinks[node] = min(lowLinks[node], lowLinks[adjacentNode])
            elif onStack[adjacentNode]:
                # we have reached the previously visited node or come back in the call stack
                lowLinks[node] = min(lowLinks[node], indices[adjacentNode])

        if lowLinks[node] == indices[node]:
            while nodeStack:
                current = nodeStack.pop()
                connectedComponentLink[current] = node
                onStack[current] = False
                connectedComponents[node] |= nodeDpPosition[current]

                if current == node:
                    break

    for i in range(1, n + 1):
        if indices[i] < 0:
            connectedComponent(i)

    return (connectedComponents, connectedComponentLink)

connectedComponents, connectedComponentLink = findAllConnectedComponents(adjacentNodes)

def advancedDfs(node):
    lowLinkNode = connectedComponentLink[node]

    neighbours = adjacentNodes.get(node)
    if neighbours is not None:
        for neighbour in neighbours:
            lowLinkNeighbourNode = connectedComponentLink[neighbour]
            if (connectedComponents[lowLinkNode] & nodeDpPosition[lowLinkNeighbourNode]) == 0:
                connectedComponents[lowLinkNode] |= nodeDpPosition[lowLinkNeighbourNode]
                advancedDfs(lowLinkNeighbourNode)

            connectedComponents[lowLinkNode] |= connectedComponents[lowLinkNeighbourNode]

for i in range(1, n + 1):
    advancedDfs(i)

for query in queries:
     x, y = query
     lowLinkXNode = connectedComponentLink[x]
     lowLinkYNode = connectedComponentLink[y]
     if connectedComponents[lowLinkXNode] & nodeDpPosition[lowLinkYNode]:
         print ("Yes")
     else:
         print ("No")