题目链接

迷宫可达任务

题目描述

给定一个由 间房间和 条单向通道组成的迷宫。你需要判断这个迷宫是否为“完美迷宫”。

一个完美迷宫的定义是：对于迷宫中任意两间不同的房间 和 ，必须满足以下两个条件之一：

  1. 是从 可达的（即存在一条从 到 的路径）。
  2. 是从 可达的（即存在一条从 到 的路径）。

简单来说，任意两点之间都必须至少存在一个单向的路径。

解题思路

这是一个图论问题。我们可以将房间和通道模型化为一个有向图。题目中的“完美迷宫”定义了一个特殊的图属性，我们需要判断给定的图是否满足这个属性。

1. 强连通分量 (SCC) 与缩点

这个问题的核心在于分析图的全局连通性。我们可以使用强连通分量 (Strongly Connected Component, SCC) 来简化图的结构。

  • SCC：图中的一个最大子集，其中任意两个节点都相互可达。
  • 缩点：我们可以将每个 SCC “压缩”成一个单一的超级节点。原图中连接不同 SCC 的边，会成为连接这些超级节点的边。这样，原图就被转换成了一个有向无環图 (DAG)，我们称之为缩点图。

2. “完美迷宫”的图论等价条件

现在，我们来分析“完美迷宫”的条件在缩点图上意味着什么。

  • 如果原图本身就是一个大的 SCC（即缩点后只有一个节点），那么任意两点都相互可达，显然满足条件。
  • 如果缩点图有多个节点，考虑任意两个不同的房间 和 ：
    • 如果 在同一个 SCC 内，它们相互可达，满足条件。
    • 如果 在不同的 SCC 中（设为 和 ），那么要满足条件，缩点图上必须存在从 到 的路径，或者从 到 的路径。

这个条件必须对任意两个 SCC 都成立。在一个 DAG 中，要让任意两个节点之间都存在单向路径，这个 DAG 的结构必须是一条简单的链（Path Graph），例如 S1 -> S2 -> S3 -> ... -> Sk。

  • 任何其他结构，比如分叉 (S1 -> S2 and S1 -> S3) 或汇合 (S2 -> S4 and S3 -> S4)，都会导致某些 SCC 之间无法相互到达。

3. 如何判断 DAG 是一条链？

一个包含 个节点的 DAG 是一条简单链，当且仅当它满足以下所有条件：

  1. 有且仅有一个节点的入度为 0（链的起点）。
  2. 有且仅有一个节点的出度为 0（链的终点）。
  3. 其余 个节点的入度和出度都必须恰好为 1。

算法整体流程

  1. 构建图：根据输入构建邻接表。
  2. 求 SCC：使用 Tarjan 算法 找出图中的所有 SCC，并记录每个节点所属的 SCC 编号。
  3. 分析缩点图： a. 如果 SCC 的总数 scc_count 为 1，说明原图强连通，直接输出 "Yes"。 b. 如果 scc_count > 1，则计算缩点图中每个 SCC 节点的入度和出度。 c. 统计满足上述链状图条件的节点数量（源点数、汇点数、中间节点数）。 d. 如果统计结果符合一个源点、一个汇点以及 scc_count - 2 个中间节点，则输出 "Yes"。否则，输出 "No"。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue> // Added for Kahn's algorithm

using namespace std;

vector<vector<int>> adj;
vector<int> dfn, low, scc_id;
stack<int> st;
vector<bool> on_stack;
int timer, scc_count;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (dfn[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (on_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++scc_count;
        int node;
        do {
            node = st.top();
            st.pop();
            on_stack[node] = false;
            scc_id[node] = scc_count;
        } while (node != u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    adj.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    scc_id.assign(n + 1, 0);
    on_stack.assign(n + 1, false);
    timer = 0;
    scc_count = 0;

    for (int i = 1; i <= n; ++i) {
        if (dfn[i] == 0) {
            tarjan(i);
        }
    }

    if (scc_count == 1) {
        cout << "Yes" << endl;
        return 0;
    }

    vector<vector<int>> scc_adj(scc_count + 1);
    vector<int> scc_in_degree(scc_count + 1, 0);
    vector<pair<int, int>> scc_edge_list;

    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                scc_edge_list.push_back({scc_id[u], scc_id[v]});
            }
        }
    }
    sort(scc_edge_list.begin(), scc_edge_list.end());
    scc_edge_list.erase(unique(scc_edge_list.begin(), scc_edge_list.end()), scc_edge_list.end());

    for(const auto& edge : scc_edge_list) {
        scc_adj[edge.first].push_back(edge.second);
        scc_in_degree[edge.second]++;
    }

    queue<int> q;
    for (int i = 1; i <= scc_count; ++i) {
        if (scc_in_degree[i] == 0) {
            q.push(i);
        }
    }

    int processed_nodes = 0;
    bool is_path = true;
    while (!q.empty()) {
        if (q.size() > 1) {
            is_path = false;
            break;
        }
        int u_scc = q.front();
        q.pop();
        processed_nodes++;

        for (int v_scc : scc_adj[u_scc]) {
            scc_in_degree[v_scc]--;
            if (scc_in_degree[v_scc] == 0) {
                q.push(v_scc);
            }
        }
    }
    
    if (is_path && processed_nodes == scc_count) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

import java.util.*;

class Main {
    static List<List<Integer>> adj;
    static int[] dfn, low, sccId;
    static boolean[] onStack;
    static Stack<Integer> stack;
    static int timer, sccCount;

    static void tarjan(int u) {
        dfn[u] = low[u] = ++timer;
        stack.push(u);
        onStack[u] = true;

        for (int v : adj.get(u)) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            sccCount++;
            int node;
            do {
                node = stack.pop();
                onStack[node] = false;
                sccId[node] = sccCount;
            } while (node != u);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
        }

        dfn = new int[n + 1];
        low = new int[n + 1];
        sccId = new int[n + 1];
        onStack = new boolean[n + 1];
        stack = new Stack<>();
        timer = 0;
        sccCount = 0;

        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) {
                tarjan(i);
            }
        }

        if (sccCount == 1) {
            System.out.println("Yes");
            return;
        }

        Map<Integer, List<Integer>> sccAdj = new HashMap<>();
        int[] sccInDegree = new int[sccCount + 1];
        Set<Long> sccEdgeSet = new HashSet<>();

        for (int u = 1; u <= n; u++) {
            for (int v : adj.get(u)) {
                if (sccId[u] != sccId[v]) {
                    long edgeHash = (long)sccId[u] << 32 | sccId[v];
                    if (!sccEdgeSet.contains(edgeHash)) {
                        sccAdj.computeIfAbsent(sccId[u], k -> new ArrayList<>()).add(sccId[v]);
                        sccInDegree[sccId[v]]++;
                        sccEdgeSet.add(edgeHash);
                    }
                }
            }
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= sccCount; i++) {
            if (sccInDegree[i] == 0) {
                q.offer(i);
            }
        }

        int processedNodes = 0;
        boolean isPath = true;
        while (!q.isEmpty()) {
            if (q.size() > 1) {
                isPath = false;
                break;
            }
            int uScc = q.poll();
            processedNodes++;

            for (int vScc : sccAdj.getOrDefault(uScc, Collections.emptyList())) {
                sccInDegree[vScc]--;
                if (sccInDegree[vScc] == 0) {
                    q.offer(vScc);
                }
            }
        }

        if (isPath && processedNodes == sccCount) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

import sys
import collections

sys.setrecursionlimit(200005)

adj = {}
dfn, low, scc_id = [], [], []
on_stack = []
stack = []
timer, scc_count = 0, 0

def tarjan(u):
    global timer, scc_count
    
    timer += 1
    dfn[u] = low[u] = timer
    stack.append(u)
    on_stack[u] = True

    for v in adj.get(u, []):
        if dfn[v] == 0:
            tarjan(v)
            low[u] = min(low[u], low[v])
        elif on_stack[v]:
            low[u] = min(low[u], dfn[v])

    if dfn[u] == low[u]:
        scc_count += 1
        while True:
            node = stack.pop()
            on_stack[node] = False
            scc_id[node] = scc_count
            if node == u:
                break

def main():
    global adj, dfn, low, scc_id, on_stack, stack, timer, scc_count
    
    try:
        n, m = map(int, sys.stdin.readline().split())
    except ValueError:
        print("No")
        return
        
    adj = {i: [] for i in range(1, n + 1)}
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        
    dfn = [0] * (n + 1)
    low = [0] * (n + 1)
    scc_id = [0] * (n + 1)
    on_stack = [False] * (n + 1)
    stack = []
    timer, scc_count = 0, 0

    for i in range(1, n + 1):
        if dfn[i] == 0:
            tarjan(i)
    
    if scc_count == 1:
        print("Yes")
        return
        
    scc_adj = {i: [] for i in range(1, scc_count + 1)}
    scc_in_degree = [0] * (scc_count + 1)
    scc_edges = set()
    
    for u in range(1, n + 1):
        for v in adj.get(u, []):
            if scc_id[u] != scc_id[v]:
                edge = (scc_id[u], scc_id[v])
                scc_edges.add(edge)
    
    for u_scc, v_scc in scc_edges:
        scc_adj[u_scc].append(v_scc)
        scc_in_degree[v_scc] += 1
            
    q = collections.deque([i for i in range(1, scc_count + 1) if scc_in_degree[i] == 0])

    processed_nodes = 0
    is_path = True
    while q:
        if len(q) > 1:
            is_path = False
            break
        
        u_scc = q.popleft()
        processed_nodes += 1
        
        for v_scc in scc_adj.get(u_scc, []):
            scc_in_degree[v_scc] -= 1
            if scc_in_degree[v_scc] == 0:
                q.append(v_scc)
            
    if is_path and processed_nodes == scc_count:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：强连通分量 (Tarjan 算法) + 缩点 + Kahn's Topological Sort
  • 时间复杂度：，其中 是房间数量， 是通道数量。算法的核心是 Tarjan 算法和对图/缩点图的遍历，均为线性时间复杂度。
  • 空间复杂度：，用于存储图的邻接表以及 Tarjan 算法所需的各种辅助数组。
  • 空间复杂度：，用于存储图的邻接表以及 Tarjan 算法所需的各种辅助数组。