Editing 2015 Jan Gold Problem 3 Grass Cownoisseur (section)

=== Python ===
<pre>
from collections import defaultdict

MAX_NODES = 100010
sccNodeIdx, sccLabel, sccStackPtr = 0, 0, 0
sccIndices = [-1]*MAX_NODES
sccLinks = [0]*MAX_NODES
sccStack = [0]*MAX_NODES
memo = [[-1]*MAX_NODES for _ in range(2)]

def collapse_graph(adjList, labels):
    numNodes = len(adjList)
    resultGraph = defaultdict(list)
    for node in range(numNodes):
        labelX = labels[node]
        for edgeNode in adjList[node]:
            labelY = labels[edgeNode]
            if labelX != labelY:
                resultGraph[labelX].append(labelY)
    for v in resultGraph.values():
        v.sort()
        v = list(dict.fromkeys(v))
    return resultGraph

def tarjanDFS(node, adjList, labels):
    global sccNodeIdx, sccLabel, sccStackPtr
    index = sccIndices[node] = sccNodeIdx
    sccNodeIdx += 1
    sccLinks[node] = index

    sccStack[sccStackPtr] = node
    sccStackPtr += 1
    for edgeNode in adjList[node]:
        if sccIndices[edgeNode] == -1:
            tarjanDFS(edgeNode, adjList, labels)
            sccLinks[node] = min(sccLinks[node], sccLinks[edgeNode])
        else:
            sccLinks[node] = min(sccLinks[node], sccIndices[edgeNode])

    if index == sccLinks[node]:
        lastNode = -1
        while lastNode != node:
            sccStackPtr -= 1
            lastNode = sccStack[sccStackPtr]
            sccIndices[lastNode] = len(adjList)
            labels[lastNode] = sccLabel
        sccLabel += 1

def computeSCC(adjList):
    global sccNodeIdx, sccLabel, sccStackPtr
    numNodes = len(adjList)
    labels = [-1]*numNodes

    sccNodeIdx = sccLabel = sccStackPtr = 0
    for node in range(numNodes):
        if labels[node] == -1:
            tarjanDFS(node, adjList, labels)
    return labels

def computeMaxWeightPath(cid, weights, adjList, startNode, targetNode):
    if startNode == targetNode:
        return 0

    if memo[cid][startNode] != -1:
        return memo[cid][startNode]

    memo[cid][startNode] = -2
    for edgeNode in adjList[startNode]:
        result = computeMaxWeightPath(cid, weights, adjList, edgeNode, targetNode)
        if result >= 0:
            memo[cid][startNode] = max(memo[cid][startNode], weights[startNode] + result)
    return memo[cid][startNode]

def main():
    numNodes, numEdges = map(int, input().split())
    adjList = defaultdict(list)
    for _ in range(numEdges):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adjList[u].append(v)

    labels = computeSCC(adjList)
    adjList = collapse_graph(adjList, labels)
    startLabel = labels[0]

    reverseAdjList = defaultdict(list)
    for node, nodeEdges in adjList.items():
        for edgeNode in nodeEdges:
            reverseAdjList[edgeNode].append(node)

    weights = [0]*len(adjList)
    for node in range(numNodes):
        weights[labels[node]] += 1

    result = weights[startLabel]
    for node in adjList:
        result1 = computeMaxWeightPath(0, weights, adjList, node, startLabel)
        if result1 < 0:
            continue
        for edgeNode in adjList[node]:
            result2 = computeMaxWeightPath(1, weights, reverseAdjList, edgeNode, startLabel)
            if result2 >= 0:
                result = max(result, weights[startLabel] + result1 + result2)
    print(result)

main()

</pre>


[[Category:Yearly_2014_2015]]
[[Category:Gold]]
[[Category:Graph]]
[[Category:Sets]]
[[Category:Depth First Search]]
[[Category:Bipartite Graph Check]]