序列重建

import java.util.*;
import java.util.stream.*;

// 思路：我们将使用拓扑排序的方法来检查 nums 是否是唯一的最短超序列。通过构建有向图和计算入度，我们可以确定唯一性。
public class Solution {
    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
        int n = nums.length;
        int[] inDegree = new int[n + 1];
        Map<Integer, List<Integer>> graph = IntStream.rangeClosed(1, n).boxed()
            .collect(Collectors.toMap(i -> i, i -> new ArrayList<>()));
        sequences.forEach(sequence -> IntStream.range(0, sequence.size() - 1).forEach(i -> {
            graph.get(sequence.get(i)).add(sequence.get(i + 1));
            inDegree[sequence.get(i + 1)]++;
        }));
        Queue<Integer> queue = IntStream.rangeClosed(1, n).filter(i -> inDegree[i] == 0).boxed()
            .collect(Collectors.toCollection(LinkedList::new));
        int index = 0;
        while (!queue.isEmpty()) {
            if (queue.size() > 1) return false;
            int current = queue.poll();
            if (nums[index++] != current) return false;
            graph.get(current).forEach(neighbor -> {
                if (--inDegree[neighbor] == 0) queue.add(neighbor);
            });
        }
        return index == n;
    }
}