2015 Jan Gold Problem 3 Grass Cownoisseur

Problem

The problem involves a directed graph representing fields (nodes) and paths (edges) connecting the fields. Every field has a certain quantity of grass (a value). The task is to find the maximum total quantity of grass a cow can eat if the cow starts from any field, moves along the paths, and cannot go through any path more than once. The cow can continue moving as long as it has not yet traversed all fields it can reach without reusing a path.

Solution

This problem can be solved by using depth-first search (DFS), strongly connected components (SCC), and dynamic programming.

The first step is to decompose the graph into strongly connected components. SCC is a subgraph in which each node is reachable from every other node.

Create a new graph with SCCs as nodes. If there exists a path between two SCCs in the original graph, connect them in the new graph. This new graph is a Directed Acyclic Graph (DAG). Each SCC is assigned a value equal to the total value of all nodes in it.

Next, we can use dynamic programming on this DAG. Start a DFS from each node and use memoization to store and re-use previously computed results. Keep track of the maximum value of grass that can be eaten starting from each SCC. Traverse all outgoing edges from the current SCC, and for each edge going to another SCC, calculate the maximum value achievable.

The answer to the problem is the maximum total grass that can be eaten starting from each SCC.

Code

C++

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define MAX_NODES 100010

using namespace std;

vector<vector<int> > CollapseGraph(const vector<vector<int> >& adjList,
                              const vector<int>& label) {
  int numNodes = adjList.size();
  vector<vector<int> > resultGraph(*max_element(label.begin(), label.end()) + 1, vector<int>());
  for(int node = 0; node < numNodes; node++) {
    int labelX = label[node];
    for(int edge : adjList[node]) {
      int labelY = label[edge];
      if(labelX != labelY) resultGraph[labelX].push_back(labelY);
    }
  }
  for(auto& v : resultGraph) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
  }
  return resultGraph;
}

int sccNodeIdx;
int sccIndices[MAX_NODES];
int sccLinks[MAX_NODES];

int sccLabel;
int sccStackPtr;
int sccStack[MAX_NODES];

void TarjanDFS(int node, const vector<vector<int> >& adjList, vector<int>& labels) {
  int index = sccIndices[node] = sccNodeIdx++;
  int& link = sccLinks[node];
  link = index;

  sccStack[sccStackPtr++] = node;
  for(int edgeNode : adjList[node]) {
    if(sccIndices[edgeNode] == -1) {
      TarjanDFS(edgeNode, adjList, labels);
      link = min(link, sccLinks[edgeNode]);
    } else {
      link = min(link, sccIndices[edgeNode]);
    }
  }

  if(index == link) {
    int y;
    do {
      y = sccStack[--sccStackPtr];
      sccIndices[y] = adjList.size();
      labels[y] = sccLabel;
    } while(y != node);
    sccLabel++;
  }
}

vector<int> ComputeSCC(const vector<vector<int> >& adjList) {
  int numNodes = adjList.size();
  vector<int> labels(numNodes, -1);

  memset(sccIndices, -1, sizeof(int) * numNodes);
  sccNodeIdx = sccLabel = sccStackPtr = 0;
  for(int node = 0; node < numNodes; node++) {
    if(labels[node] == -1) {
      TarjanDFS(node, adjList, labels);
    }
  }
  return labels;
}

int memo[2][100010];

int ComputeMaxWeightPath(int cid, const vector<int>& weights,
          const vector<vector<int> >& adjList, int start, int target) {
  if (start == target) {
    return 0;
  }

  int& ref = memo[cid][start];
  if (ref != -1) {
    return ref;
  }

  ref = -2;
  for (int nextNode : adjList[start]) {
    int res = ComputeMaxWeightPath(cid, weights, adjList, nextNode, target);
    if (res >= 0) {
      ref = max(ref, weights[start] + res);
    }
  }
  return ref;
}

int main() {
  int numNodes, numEdges;
  cin >> numNodes >> numEdges;

  vector<vector<int> > adjList(numNodes);
  for (int i = 0; i < numEdges; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    adjList[u].push_back(v);
  }

  vector<int> labels = ComputeSCC(adjList);
  adjList = CollapseGraph(adjList, labels);
  int startLabel = labels[0];

  vector<vector<int> > reverseAdjList(adjList.size());
  for (int node = 0; node < adjList.size(); node++) {
    for (int edgeNode : adjList[node]) {
      reverseAdjList[edgeNode].push_back(node);
    }
  }

  vector<int> weights(adjList.size(), 0);
  for (int node = 0; node < numNodes; node++) {
    weights[labels[node]]++;
  }

  int maxWeight = weights[startLabel];
  memset(memo, -1, sizeof(memo));
  for (int node = 0; node < adjList.size(); node++) {
    int path1 = ComputeMaxWeightPath(0, weights, adjList, node, startLabel);
    if (path1 < 0) {
      continue;
    }
    for (int nextNode : adjList[node]) {
      int path2 = ComputeMaxWeightPath(1, weights, reverseAdjList, nextNode, startLabel);
      if (path2 >= 0) {
        maxWeight = max(maxWeight, weights[startLabel] + path1 + path2);
      }
    }
  }

  cout << maxWeight << endl;

  return 0;
}

Java

import java.util.*;

public class Main {
    static final int MAX_NODES = 100010;
    static int sccNodeIdx, sccLabel, sccStackPtr;
    static int[] sccIndices = new int[MAX_NODES];
    static int[] sccLinks = new int[MAX_NODES];
    static int[] sccStack = new int[MAX_NODES];
    static int[][] memo = new int[2][MAX_NODES];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numNodes = sc.nextInt();
        int numEdges = sc.nextInt();
        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
        for(int i = 0; i < numNodes; i++) adjList.add(new ArrayList<>());
        for(int i = 0; i < numEdges; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            adjList.get(u).add(v);
        }

        ArrayList<Integer> labels = computeSCC(adjList);
        adjList = collapseGraph(adjList, labels);
        int startLabel = labels.get(0);

        ArrayList<ArrayList<Integer>> reverseAdjList = new ArrayList<>();
        for(int i = 0; i < adjList.size(); i++) reverseAdjList.add(new ArrayList<>());
        for(int node = 0; node < adjList.size(); node++)
            for(int edgeNode : adjList.get(node))
                reverseAdjList.get(edgeNode).add(node);

        ArrayList<Integer> weights = new ArrayList<>(Collections.nCopies(adjList.size(), 0));
        for(int node = 0; node < numNodes; node++) weights.set(labels.get(node), weights.get(labels.get(node)) + 1);

        int maxWeight = weights.get(startLabel);
        for(int[] row : memo) Arrays.fill(row, -1);
        for(int node = 0; node < adjList.size(); node++) {
            int path1 = computeMaxWeightPath(0, weights, adjList, node, startLabel);
            if(path1 < 0) continue;
            for(int nextNode : adjList.get(node)) {
                int path2 = computeMaxWeightPath(1, weights, reverseAdjList, nextNode, startLabel);
                if(path2 >= 0)
                    maxWeight = Math.max(maxWeight, weights.get(startLabel) + path1 + path2);
            }
        }

        System.out.println(maxWeight);
    }

    static ArrayList<ArrayList<Integer>> collapseGraph(ArrayList<ArrayList<Integer>> adjList, ArrayList<Integer> labels) {
        int numNodes = adjList.size();
        ArrayList<ArrayList<Integer>> resultGraph = new ArrayList<>();
        for(int i = 0; i < Collections.max(labels) + 1; i++) resultGraph.add(new ArrayList<>());
        for(int node = 0; node < numNodes; node++) {
            int labelX = labels.get(node);
            for(int edgeNode : adjList.get(node)) {
                int labelY = labels.get(edgeNode);
                if(labelX != labelY) resultGraph.get(labelX).add(labelY);
            }
        }
        for(ArrayList<Integer> v : resultGraph) {
            Collections.sort(v);
            v = new ArrayList<>(new LinkedHashSet<>(v));
        }
        return resultGraph;
    }

    static void tarjanDFS(int node, ArrayList<ArrayList<Integer>> adjList, ArrayList<Integer> labels) {
        int index = sccIndices[node] = sccNodeIdx++;
        sccLinks[node] = index;

        sccStack[sccStackPtr++] = node;
        for(int edgeNode : adjList.get(node)) {
            if(sccIndices[edgeNode] == -1) {
                tarjanDFS(edgeNode, adjList, labels);
                sccLinks[node] = Math.min(sccLinks[node], sccLinks[edgeNode]);
            } else {
                sccLinks[node] = Math.min(sccLinks[node], sccIndices[edgeNode]);
            }
        }

        if(index == sccLinks[node]) {
            int lastNode;
            do {
                lastNode = sccStack[--sccStackPtr];
                sccIndices[lastNode] = adjList.size();
                labels.set(lastNode, sccLabel);
            } while(lastNode != node);
            sccLabel++;
        }
    }

    static ArrayList<Integer> computeSCC(ArrayList<ArrayList<Integer>> adjList) {
        int numNodes = adjList.size();
        ArrayList<Integer> labels = new ArrayList<>(Collections.nCopies(numNodes, -1));

        Arrays.fill(sccIndices, -1);
        sccNodeIdx = sccLabel = sccStackPtr = 0;
        for(int node = 0; node < numNodes; node++)
            if(labels.get(node) == -1) tarjanDFS(node, adjList, labels);
        return labels;
    }

    static int computeMaxWeightPath(int cid, ArrayList<Integer> weights, ArrayList<ArrayList<Integer>> adjList, int startNode, int targetNode) {
        if(startNode == targetNode) return 0;

        if(memo[cid][startNode] != -1) return memo[cid][startNode];

        memo[cid][startNode] = -2;
        for(int edgeNode : adjList.get(startNode)) {
            int result = computeMaxWeightPath(cid, weights, adjList, edgeNode, targetNode);
            if(result >= 0) memo[cid][startNode] = Math.max(memo[cid][startNode], weights.get(startNode) + result);
        }
        return memo[cid][startNode];
    }
}

Python

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()