To solve the problem of finding the longest chain in a subcontracting network, we need to determine the longest sequence of companies where each company in the sequence subcontracts to the next. This involves modeling the subcontracting relationships as a directed acyclic graph (DAG) and finding the longest path in this graph.

1. Graph Representation: Represent the subcontracting relationships as a directed graph where each node is a company, and each directed edge from company A to company B indicates that A subcontracts to B.
2. Topological Sorting: Since the graph is acyclic (as a company cannot subcontract to itself or form a cycle), we can use topological sorting to process nodes in an order where all dependencies (incoming edges) are resolved before processing a node.
3. Dynamic Programming: Use dynamic programming to compute the longest chain ending at each node. For each node, the longest chain ending at that node is one more than the longest chain ending at any of its predecessors.
4. Cycle Detection: Ensure the graph is acyclic by checking if all nodes are processed during the topological sort. If any node remains unprocessed, it indicates a cycle, which is invalid for subcontracting chains.

Solution Code

from collections import deque
def longest_subcontract_chain(graph):
    nodes = set()
    for u in graph:
        nodes.add(u)
        for v in graph[u]:
            nodes.add(v)
    if not nodes:
        return 0
    in_degree = {node: 0 for node in nodes}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    dp = {node: 1 for node in nodes}
    queue = deque()
    for node in nodes:
        if in_degree[node] == 0:
            queue.append(node)
    while queue:
        u = queue.popleft()
        if u in graph:
            for v in graph[u]:
                if dp[u] + 1 > dp[v]:
                    dp[v] = dp[u] + 1
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
    return max(dp.values())

Explanation

1. Graph Representation: The graph is built from the input dictionary where keys are companies and values are lists of companies they subcontract to. All nodes (companies) are collected into a set to ensure every company is accounted for, even if it has no outgoing edges.
2. In-Degree Calculation: The in-degree of each node (number of incoming edges) is calculated. Nodes with zero in-degree are starting points for chains.
3. Topological Sort: Nodes are processed in topological order using a queue. Nodes with zero in-degree are processed first.
4. Dynamic Programming: For each node processed, the longest chain ending at its neighbors is updated. If processing a node reduces the in-degree of a neighbor to zero, that neighbor is added to the queue.
5. Result Extraction: The maximum value in the dynamic programming array dp gives the length of the longest subcontract chain, as dp[node] stores the longest chain ending at node.

This approach efficiently computes the longest chain by leveraging topological sorting and dynamic programming, ensuring optimal performance for acyclic graphs. The solution handles disconnected components and ensures correctness by validating the absence of cycles.