跳至主要內容

欧拉图

大约 3 分钟

欧拉图

题目难度
332. 重新安排行程open in new window困难
753. 破解保险箱open in new window困难
2097. 合法重新排列数对open in new window困难T4

定义

通过图中所有边恰好一次的通路称为欧拉通路。

通过图中所有边恰好一次的回路称为欧拉回路。

具有欧拉回路的无向图或有向图称为欧拉图。

Hierholzer 算法

332. 重新安排行程

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution332 {
    // 如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
    private Map<String, PriorityQueue<String>> adj;
    private List<String> resList;

    public List<String> findItinerary(List<List<String>> tickets) {
        adj = new HashMap<>();
        for (List<String> ticket : tickets) {
            String u = ticket.get(0);
            String v = ticket.get(1);
            adj.computeIfAbsent(u, key -> new PriorityQueue<>()).add(v);
        }
        resList = new ArrayList<>();

        // 欧拉通路 / 欧拉回路
        // 该行程必须从 JFK 开始
        dfs("JFK");
        Collections.reverse(resList);
        return resList;
    }

    private void dfs(String u) {
        // 当我们遍历完一个节点所连的所有节点后，我们才将该节点入队（即逆序入队）
        while (adj.containsKey(u) && adj.get(u).size() > 0) {
            String v = adj.get(u).poll();
            dfs(v);
        }
        resList.add(u);
    }
}

753. 破解保险箱

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution753 {
    private StringBuilder ans;
    private Map<String, Queue<String[]>> adj;

    // 假设 k = 4, n = 3 时，节点分别为 00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33，
    // 每个节点的出边的编号分别为 0, 1, 2, 3，
    // 那么 00 和它的出边形成了 000, 001, 002, 003 这 4 个 3 位数，32 和它的出边形成了 320, 321, 322, 323 这 4 个 3 位数
    // 形成一个有向图，16 个节点，64 条边，每个节点 4 条出边，4 条入边
    public String crackSafe(int n, int k) {
        ans = new StringBuilder();

        // 0,1,···,k-1
        String[] ss = new String[k];
        String[] permute = {""};
        for (int i = 0; i < k; i++) {
            ss[i] = String.valueOf(i);
        }
        for (int i = 0; i < n - 1; i++) {
            permute = cartesianProduct(permute, ss);
        }

        // 建图
        adj = new HashMap<>();
        for (String u : permute) {
            for (int x = 0; x < k; x++) {
                String v = (u + x).substring(1);
                String w = String.valueOf(x);
                adj.computeIfAbsent(u, key -> new LinkedList<>()).add(new String[]{v, w});
            }
        }
        // 欧拉回路
        dfs(permute[0]);
        return ans.toString() + permute[0];
    }

    private void dfs(String u) {
        while (adj.containsKey(u) && adj.get(u).size() > 0) {
            String[] v = adj.get(u).remove();
            dfs(v[0]);
            ans.append(v[1]);
        }
    }

    // 笛卡尔积
    private String[] cartesianProduct(String[] arr1, String[] arr2) {
        int len = arr1.length * arr2.length;
        String[] res = new String[len];
        int id = 0;
        for (String s1 : arr1) {
            for (String s2 : arr2) {
                res[id++] = s1 + s2;
            }
        }
        return res;
    }

    private int k;
    private Set<Integer> seen;
    private StringBuilder stringBuilder;
    private int highest;

    // 官方解
    public String crackSafe2(int n, int k) {
        this.k = k;
        seen = new HashSet<>();
        stringBuilder = new StringBuilder();
        // 10^(n-1)
        highest = (int) Math.pow(10, n - 1);

        dfs(0);
        stringBuilder.append("0".repeat(n - 1));
        return stringBuilder.toString();
    }

    private void dfs(int u) {
        for (int x = 0; x < k; x++) {
            int v = u * 10 + x;
            if (!seen.contains(v)) {
                seen.add(v);
                dfs(v % highest);
                stringBuilder.append(x);
            }
        }
    }
}

2097. 合法重新排列数对

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution2097 {
    private Map<Integer, Queue<Integer>> adj;
    private List<int[]> resList;

    public int[][] validArrangement(int[][] pairs) {
        Map<Integer, Integer> degreeMap = new HashMap<>();
        adj = new HashMap<>();
        for (int[] pair : pairs) {
            int u = pair[0];
            int v = pair[1];
            adj.computeIfAbsent(u, key -> new LinkedList<>()).add(v);
            // 出度 -1 入度 +1
            degreeMap.put(u, degreeMap.getOrDefault(u, 0) - 1);
            degreeMap.put(v, degreeMap.getOrDefault(v, 0) + 1);
        }
        resList = new ArrayList<>();

        // 欧拉通路
        // 恰有一个顶点 出度 = 入度 + 1（起点） && 恰有一个顶点 入度 = 出度 + 1（终点）
        // dfs 起点
        for (Map.Entry<Integer, Integer> entry : degreeMap.entrySet()) {
            if (entry.getValue() == -1) {
                dfs(entry.getKey());
                Collections.reverse(resList);
                return resList.toArray(int[][]::new);
            }
        }

        // 欧拉回路
        // 每个顶点的入度和出度相同
        // dfs 任意点
        dfs(pairs[0][0]);
        Collections.reverse(resList);
        return resList.toArray(int[][]::new);
    }

    private void dfs(int u) {
        // 当我们遍历完一个节点所连的所有节点后，我们才将该节点入队（即逆序入队）
        while (adj.containsKey(u) && adj.get(u).size() > 0) {
            int v = adj.get(u).remove();
            dfs(v);
            resList.add(new int[]{u, v});
        }
    }
}

（全文完）

Copyright © 2018-2023 gdut-yy