迷宫 - 题目列表

题意

多组数据。每组给若干条边（房间号对），以 0 0 结束；整个文件以 -1 -1 结束。

判断设计图是否符合要求：任意两个房间有且仅有一条路径可以相通。符合输出 1，否则输出 0。

思路

最直接的想法是建图后暴力检查：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 11:30
 * update_at: 2026-08-05 11:30
 */
// brute.cpp：小数据暴力解，对每组数据建邻接表，
// 用 BFS 判连通 + DFS 判环，与并查集解法独立实现。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

vector<int> g[MAXN];    // 邻接表
bool appear[MAXN];
bool vis[MAXN];
vector<int> nodes;      // 本组出现的所有节点

// BFS：从 start 出发，统计能到达的节点数
int bfs_count(int start) {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(start);
    vis[start] = true;
    int cnt = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                cnt++;
                q.push(v);
            }
        }
    }
    return cnt;
}

// DFS 判环：从 u 出发，若访问到已在当前栈中的点则有环
bool dfs_cycle(int u, int parent) {
    vis[u] = true;
    for (int v : g[u]) {
        if (v == parent) continue;   // 忽略回父亲的边（无向图）
        if (vis[v]) return true;     // 访问到已访问过的点：有环
        if (dfs_cycle(v, u)) return true;
    }
    return false;
}

// 清空本组数据的邻接表和标记
void clear_all() {
    for (int x : nodes) {
        g[x].clear();
        appear[x] = false;
    }
    nodes.clear();
}

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

    int u, v;
    while (cin >> u >> v) {
        if (u == -1 && v == -1) break;
        if (u == 0 && v == 0) {
            bool ok = true;
            if (!nodes.empty()) {
                // 判环
                memset(vis, 0, sizeof(vis));
                if (dfs_cycle(nodes[0], -1)) ok = false;
                // 判连通：BFS 能到达的节点数 == 出现节点总数
                int reach = bfs_count(nodes[0]);
                if (reach != (int)nodes.size()) ok = false;
            }
            cout << (ok ? 1 : 0) << '\n';
            clear_all();
            continue;
        }

        if (!appear[u]) { appear[u] = true; nodes.push_back(u); }
        if (!appear[v]) { appear[v] = true; nodes.push_back(v); }
        g[u].push_back(v);
        g[v].push_back(u);
    }

    return 0;
}

暴力做法对每组数据建邻接表，用 DFS 判环、BFS 判连通。正确但每次都要遍历整张图。

关键观察：“任意两点有且仅有一条路径” ⇔ 这张无向图是一棵树 ⇔ 同时满足两个条件：

无环：加边时若两端点已经连通，说明这条边形成了环；
连通：所有出现过的房间在同一个集合里。

树的性质正好可以用并查集在线判断：

text

1
2
3
4
5
6加边 (u, v):
  ├─ find(u) == find(v) → 已经连通 → 有环 → 不合法
  └─ 否则合并两个集合

一组数据结束：
  所有出现过的节点必须属于同一个根（连通）

以样例第三组为例，边依次为 $(3,8)(6,8)(6,4)(5,3)(5,6)(5,2)$ ，其中 $5$ 到 $8$ 有两条路径（ $5\to 3\to 8$ 和 $5\to 6\to 8$ ），加某条边时会发现两端点已在同一集合，输出 0。

注意边界：一组数据没有边（直接 0 0）是合法的空树，输出 1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 11:30
 * update_at: 2026-08-05 11:30
 */
// 并查集：迷宫合法当且仅当 无环 且 所有出现过的房间连通（即是一棵树）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int fa[MAXN];          // 并查集父节点
bool appear[MAXN];     // 该房间编号是否在本组数据中出现过

void init() {
    for (int i = 1; i <= 100000; i++) fa[i] = i;
    memset(appear, 0, sizeof(appear));
}

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);   // 路径压缩
}

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

    init();
    bool has_edge = false;    // 本组数据是否至少有一条边
    bool ok = true;           // 是否满足无环且连通

    int u, v;
    while (cin >> u >> v) {
        if (u == -1 && v == -1) break;   // 整个文件结束
        if (u == 0 && v == 0) {          // 一组数据结束
            // 有边时检查连通：找一个出现过的节点做基准根
            int root = -1;
            for (int i = 1; i <= 100000; i++) {
                if (appear[i]) {
                    root = find(i);
                    break;
                }
            }
            // 所有出现过的节点必须在同一个集合里
            if (root != -1) {
                for (int i = 1; i <= 100000; i++) {
                    if (appear[i] && find(i) != root) {
                        ok = false;
                        break;
                    }
                }
            }
            cout << (ok ? 1 : 0) << '\n';
            init();
            has_edge = false;
            ok = true;
            continue;
        }

        // 本组数据内的一条边
        has_edge = true;
        appear[u] = true;
        appear[v] = true;
        int ru = find(u), rv = find(v);
        if (ru == rv) ok = false;   // 两点已经连通：出现环
        else fa[ru] = rv;
    }

    return 0;
}

复杂度

并查集带路径压缩，每组数据每条边 $O(\alpha(n))$ 近似 $O(1)$ ，时间 $O(\text{边数})$ ；空间 $O(10^5)$ 。

总结

“任意两点唯一路径” = 树的特征。用并查集判断"树"的通用套路：

加边时检查两端是否已连通（判环）；
结束后检查所有出现节点是否同根（判连通）。

图示解析

text

1
2
3
4
5合法（树）                    非法（有环）
1──2──3                     5──3──8
   │                          │  ╱
   4                         6──4
任意两点只有一条路           5 到 8 有两条路

读图方法：左边没有环且连通，任意两点唯一路径；右边节点 $5,8$ 之间存在两条不同路径，加边时必然出现"两端点已连通"的冲突。

迷宫

目录

题意

思路

代码

复杂度

总结

图示解析