給定一個長度為 n 的整數(shù)數(shù)組 nums 悯舟，其中 nums 是范圍為 [1担租，n] 的整數(shù)的排列。還提供了一個 2D 整數(shù)數(shù)組 sequences 抵怎，其中 sequences[i] 是 nums 的子序列奋救。
檢查 nums 是否是唯一的最短 超序列 。最短 超序列 是 長度最短 的序列反惕，并且所有序列 sequences[i] 都是它的子序列尝艘。對于給定的數(shù)組 sequences ，可能存在多個有效的 超序列 姿染。
例如背亥，對于 sequences = [[1,2],[1,3]] ，有兩個最短的 超序列 ，[1,2,3] 和 [1,3,2] 狡汉。
而對于 sequences = [[1,2],[1,3],[1,2,3]] 娄徊，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列盾戴，但不是最短的寄锐。
如果 nums 是序列的唯一最短 超序列 ，則返回 true 捻脖，否則返回 false 锐峭。
子序列 是一個可以通過從另一個序列中刪除一些元素或不刪除任何元素，而不改變其余元素的順序的序列可婶。
示例 1：
輸入：nums = [1,2,3], sequences = [[1,2],[1,3]]
輸出：false
解釋：有兩種可能的超序列：[1,2,3]和[1,3,2]沿癞。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列矛渴。
因?yàn)?nums 不是唯一最短的超序列椎扬，所以返回false。
class Solution {
public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
int n = nums.length;
int[] indegrees = new int[n + 1];
Set<Integer>[] graph = new Set[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new HashSet<Integer>();
}
for (int[] sequence : sequences) {
int size = sequence.length;
for (int i = 1; i < size; i++) {
int prev = sequence[i - 1], next = sequence[i];
if (graph[prev].add(next)) {
indegrees[next]++;
}
}
}
Queue<Integer> queue = new ArrayDeque<Integer>();
for (int i = 1; i <= n; i++) {
if (indegrees[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
if (queue.size() > 1) {
return false;
}
int num = queue.poll();
Set<Integer> set = graph[num];
for (int next : set) {
indegrees[next]--;
if (indegrees[next] == 0) {
queue.offer(next);
}
}
}
return true;
}
}
