Editing 2015 Jan Gold Problem 3 Grass Cownoisseur (section)

== Code ==

=== C++ ===
<pre>
#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;
}

</pre>

=== Java ===
<pre>
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];
    }
}

</pre>


=== 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]]