题目描述

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

样例

Example 1:

Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
Example 2:

Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be [1,2].
Example 3:

Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Example 4:

Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:
true

/**
1. "按顺序在序列集 seqs 中构建最短且唯一的公共超序列org", 这个题目内容太抽象精简了,分解一下: 
1.1 序列集 seqs 中构建org  ->  seqs 是有序的可根据二元关系建立有向图
1.2 org为seqs 的公共超序列 ->  org的元素集合必定和seqs的元素全集一一对应且相等
1.3 org为最短公共超序列    ->  org 为有向图中的最长路
1.4 org为唯一公共超序列    ->  有向图中只有一条最长路,并且恰好为org


2. 为满足上述4个要求, 可以深搜统计长度>= org.length 的路的数量
2.1 搜索顺序: 搜索当前可达到的路径, 判断是否与org相等, 相等返回1个, 不等返回2个
2.2 搜索状态: local: point, index | global: graph, org, buffer
2.3 剪枝:   
    2.3.1 长度相等且路径不同的路径直接返回 2
    2.3.2 长度 > org.length 的路径直接返回2
    2.3.3 某子分支已经返回2 就直接返回2
2.4 此时要对边去重, 防止重复扫描

3. 也可以拓扑排序: 
3.1 因为唯一最长路, 所以queue 中最多只能有一个元素
3.2 结果必须完全相等

4.吐槽下, 这个应该是m+ ~ hard难度的

*/

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> graph = build(org, seqs);
        if (graph == null) return false;
        return topSort(graph, org);
        // return search(graph, org);
    }

    public boolean topSort(Map<Integer, Set<Integer>>graph, int[] org){
        Map<Integer, Integer> ins = new HashMap<>();
        for (Integer x : graph.keySet()){
            for (Integer y: graph.get(x)){
                if (ins.get(y) == null) ins.put(y, 0);
                ins.put(y, ins.get(y) + 1);
            }
        }
        int start = org[0], cur = 0;
        if (ins.get(start) != null) return false;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()){
            if(queue.size() > 1) return false;

            int top = queue.poll();
            if (cur >= org.length ) return false;
            if (org[cur] != top ) return false;
            cur ++ ;
            Set<Integer> edge = graph.get(top);
            for (Integer y : edge){
                ins.put(y, ins.get(y)-1);
                if (ins.get(y) == 0) queue.offer(y);
            }
        }    
        return cur == org.length;
    }

    public Map<Integer, Set<Integer>> build(int[] org, List<List<Integer>> seqs){
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0 ; i < org.length ; i++) set.add(org[i]);

        for (int i = 0; i < seqs.size(); i ++){
            List<Integer> seq = seqs.get(i);
            for (int j = 0 ; j < seq.size(); j++) {
                int x = seq.get(j);
                if (!set.contains(x)) return null;
                if (!graph.containsKey(x)) graph.put(x, new HashSet<Integer>());
            }
            for (int j = 0 ; j < seq.size()-1 ; j++){
                int x = seq.get(j);
                int y = seq.get(j+1);
                graph.get(x).add(y);
            }
        }
        if (!graph.containsKey(org[0])) return null;
        return graph;
    }

    public boolean search(Map<Integer, Set<Integer>> graph, int[] org){
        List<Integer> buffer = new ArrayList<>();
        buffer.add(org[0]);
        int count = dfs(org[0], 0, graph, org, buffer);
        return count == 1;
    }

    public int dfs(int s, int cur, Map<Integer, Set<Integer>> graph, int[] org, List<Integer> buffer ){
        if (buffer.size() > org.length)  return 2;

        Set<Integer> edge = graph.get(s);
        if ( buffer.size() == org.length &&  edge.isEmpty() ){
            for (int i = 0 ; i < buffer.size(); i ++)
                if (org[i] != buffer.get(i))
                     return 2;
            return 1;
        }

        int count = 0;
        if (edge.isEmpty()) return 0;

        for (Integer y : edge){
            buffer.add(y);
            int r = dfs(y, cur + 1, graph, org, buffer);
            buffer.remove(buffer.size()-1);
            if (r == 1) count ++ ;
            else if (r == 2) return 2;
        }
        return count;
    }
}