序列重建

/*
 * Problem: Sequence Reconstruction
 * Given an original sequence org and a list of sequences seqs, write a method to determine if org can be uniquely reconstructed from the sequences in seqs. The original sequence org is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building the shortest common supersequence of the sequences in seqs (i.e., a sequence that has all sequences in seqs as subsequences) and it should be unique.
 * 
 * Approach:
 * 1. Use a graph to represent dependencies between elements.
 * 2. Use a topological sort to determine if there's a unique way to reconstruct the sequence.
 */
 
import java.util.*;
import java.util.stream.*;
 
public class SequenceReconstruction {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        if (org.length == 0 || seqs.size() == 0) return false;
 
        Map<Integer, Set<Integer>> graph = Arrays.stream(org).boxed().collect(Collectors.toMap(k -> k, v -> new HashSet<>()));
        Map<Integer, Integer> inDegree = Arrays.stream(org).boxed().collect(Collectors.toMap(k -> k, v -> 0));
 
        int count = seqs.stream().mapToInt(List::size).sum();
        if (count < org.length) return false;
 
        for (List<Integer> seq : seqs) {
            for (int i = 0; i < seq.size(); i++) {
                if (!graph.containsKey(seq.get(i))) return false;
                if (i > 0) {
                    int prev = seq.get(i - 1);
                    int curr = seq.get(i);
                    if (graph.get(prev).add(curr)) {
                        inDegree.put(curr, inDegree.get(curr) + 1);
                    }
                }
            }
        }
 
        Queue<Integer> queue = inDegree.entrySet().stream()
                .filter(entry -> entry.getValue() == 0)
                .map(Map.Entry::getKey)
                .collect(Collectors.toCollection(LinkedList::new));
 
        int index = 0;
        while (!queue.isEmpty()) {
            if (queue.size() > 1) return false;
            int curr = queue.poll();
            if (org[index] != curr) return false;
            index++;
            for (int next : graph.get(curr)) {
                inDegree.put(next, inDegree.get(next) - 1);
                if (inDegree.get(next) == 0) {
                    queue.add(next);
                }
            }
        }
 
        return index == org.length;
    }
}