leetcode并查集、拓扑排序两题


685. 冗余连接 II

在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。

输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。

返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

image-20220317154627715

image-20220317154654261

题解

这个题挺难的。

最后具体分为几种情况:

  • 有冲突,无环。要把最后的冲突边记录一下,最后返回冲突边。

    image-20220317155128128

  • 有环,无冲突。记录最后的成环的边,最后返回。

    image-20220317155025350

  • 有冲突,有环。说明冲突边的终点结点1还是在环里的,此时,要把1和它的父亲结点这条边去掉,既要去环,也要去冲突。

    image-20220317155108901

class Solution {
    private int[] father;
    private int getFather(int k) {
        while(father[k]!=k) {
            //father[k]
            k = father[k];
        }
        return father[k];
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        father = new int[n+1];
        for(int i=1;i<=n;i++) {
            father[i] = i;
        }
        int conflict = -1;
        int circle = -1;
        for(int i=0;i<n;i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            if(father[v]!=v) {
                //表示已经有父亲了,又来一个父亲,不行
                conflict = i;
                continue;
            } else if(getFather(u)==getFather(v)) {
                // 排除一个人两个父亲的情况之后,父亲还相等,那就是环了
                circle = i;
                continue;
            }
            father[v] = u;
        }
        if(circle==-1) {
            return edges[conflict];
        }
        if(conflict==-1) {
            return edges[circle];
        }
        return new int[]{father[edges[conflict][1]],edges[conflict][1]};
    }
}

1591. 奇怪的打印机 II

给你一个奇怪的打印机,它有如下两个特殊的打印规则:

每一次操作时,打印机会用同一种颜色打印一个矩形的形状,每次打印会覆盖矩形对应格子里原本的颜色。 一旦矩形根据上面的规则使用了一种颜色,那么 相同的颜色不能再被使用 。 给你一个初始没有颜色的 m x n 的矩形 targetGrid ,其中 targetGrid[row][col] 是位置 (row, col) 的颜色。

如果你能按照上述规则打印出矩形 targetGrid ,请你返回 true ,否则返回 false 。

提示:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

image-20220317162523432

本来想用个取巧的方法,结果顺序不一定是从1到60。

image-20220317162709089

这种也被认为是对的,没考虑到。

错误答案

class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        // 主要是两点:1 相同颜色不能再被使用,也就是例如找3,
        //      一次得把3全部找出来,判断能不能涂成一个矩形(没被三占的地方要比3大)
        // 2 新颜色会覆盖旧颜色,所以还是上面那个说法
        int top;
        int bottom;
        int left;
        int right;
        for(int k=1;k<=60;k++) {
            top = targetGrid.length;
            bottom = -1;
            left = targetGrid[0].length;
            right = -1;
            for(int i=0;i<targetGrid.length;i++) {
                for(int j=0;j<targetGrid[0].length;j++) {
                    if(targetGrid[i][j]==k) {
                        top = Math.min(i,top);
                        bottom = Math.max(i,bottom);
                        left = Math.min(j,left);
                        right = Math.max(j,right);
                    }
                }
            }
            for(int i=top;i<=bottom;i++) {
                for(int j=left;j<=right;j++) {
                    if(targetGrid[i][j]<k) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

拓扑排序

class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        // 主要是两点:1 相同颜色不能再被使用,也就是例如找3,
        //      一次得把3全部找出来,判断能不能涂成一个矩形(没被三占的地方要比3大)
        // 2 新颜色会覆盖旧颜色,所以还是上面那个说法
        int top;
        int bottom;
        int left;
        int right;
        int[] indegree = new int[61];
        List<List<Integer>> out = new ArrayList<>();
        for(int k=0;k<=60;k++) {
            out.add(new ArrayList<>());
        }
        for(int k=1;k<=60;k++) {
            top = targetGrid.length;
            bottom = -1;
            left = targetGrid[0].length;
            right = -1;
            // 找到当前k的区域矩形
            for(int i=0;i<targetGrid.length;i++) {
                for(int j=0;j<targetGrid[0].length;j++) {
                    if(targetGrid[i][j]==k) {
                        top = Math.min(i,top);
                        bottom = Math.max(i,bottom);
                        left = Math.min(j,left);
                        right = Math.max(j,right);
                    }
                }
            }
            for(int i=top;i<=bottom;i++) {
                for(int j=left;j<=right;j++) {
                    if(targetGrid[i][j]!=k) {
                        indegree[targetGrid[i][j]]++;
                        out.get(k).add(targetGrid[i][j]);
                    }
                }
            }
        }
        Deque<Integer> deque = new LinkedList<>();
        Set<Integer> alreadyPaint = new HashSet<>();
        for(int k=1;k<=60;k++) {
            if(indegree[k]==0) {
                deque.addLast(k);
            }
        }
        while(!deque.isEmpty()) {
            int cur = deque.pollFirst();
            alreadyPaint.add(cur);
            for(int o:out.get(cur)) {
                indegree[o]--;
                if(indegree[o]==0) {
                    deque.addLast(o);
                }
            }
        }
        return alreadyPaint.size()==60;
    }
}