瑞瑞的木棍

标签: #trie #hash #欧拉路 #stl
原题目: luogu-P1333
简要描述:

这道题是 欧拉路判定 的进阶版。

本质与上一题（P1341）完全一致，只是多了两个预处理步骤。

核心解题逻辑

1. 建模 (Mapping)

  • 点：颜色（字符串）。
  • 边：木棍（连接两个颜色）。
  • 目标：一笔画（欧拉路/回路）。

2. 难点与对策

这道题不需要输出路径，只需要判断 Possible 或 Impossible。

  1. 字符串处理：
  • 颜色是字符串，无法直接用数组下标存度数。
  • 对策：使用 Trie 树 (字典树) 或 map 将字符串映射为数字 ID ()。鉴于数据量（25w条边，50w个点），Trie 效率最高。
  1. 连通性判定：
  • 所有木棍必须连在一起，不能有两堆互不相干的木棍。
  • 对策：使用 并查集 (Disjoint Set Union, DSU)。每读入一根木棍，就将两端的颜色所在的集合合并。最后检查是否只有一个“祖宗”。

3. 判定条件 (Checklist)

必须 同时 满足以下两点：

  1. 连通性：所有度数不为0的点，必须在同一个并查集中（即根节点只有一个）。
  2. 奇点数：度数为奇数的点只能是 0个（欧拉回路）或 2个（欧拉路）。

C++ 代码实现 (hash + 并查集)

cpp
copy 
        
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
91
92
93
94
95

        /**
 * Author by Rainboy blog: https://blog.roj.ac.cn github : https://github.com/rainboylvx
 * date: 2025-12-19 08:58:38
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int deg[maxn]; //桶

const ll p = 131;
ll strhash(std::string s) {
    ll res = 1;
    for( auto c : s) res = res * p + c;
    return res;
}
ll mod = 1e6+1;
ll cnt_odd_deg  = 0;


// 并查集
int fa[maxn];
int find(int id) {
    if( id == fa[id]) return id;
    return fa[id] = find(fa[id]);
}

void merge(int x,int y) {
    int fx = find(x);
    int fy = find(y);
    if( fx != fy) fa[fx] = fy;
}

void init(){
    std::string s1,s2;
    while (cin >> s1 >> s2) {
        auto h1 = strhash(s1);
        auto h2 = strhash(s2);

        int id1 = h1 % mod;
        int id2 = h2 % mod;

        deg[id1]++;
        deg[id2]++;

        //合并到一个集合
        // std::cout << s1 << " ";
        // std::cout << s2 << "\n";
        merge(id1,id2);
    }

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);

    for(int i = 0;i <= mod ;++i ) // i: 0->mod
    {
        fa[i] = i;
    }

    init();

    for(int i = 0;i <= mod ;++i ) // i: 1->n
    {
        if( deg[i] % 2 == 1) cnt_odd_deg++;
    }

    if( cnt_odd_deg !=0 && cnt_odd_deg !=2 ){
        cout << "Impossible" << endl;
        return 0;
    }

    
    int root = -1;
    //查找所有点的root 是一样的 
    for(int i = 0;i <= mod ;++i ) // i: 1->n
    {
        if( deg[i] != 0 ) {
            int ri =  find(i);
            if( root == -1) root = ri;

            if( ri != root) {
                cout << "Impossible" << endl;
                return 0;
            }
        }
    }
    cout << "Possible" << endl;
    return 0;
}

C++ 代码实现 (Trie + 并查集)

代码注重逻辑清晰，分为：映射部分、并查集部分、主逻辑。

cpp
copy 
        
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104

        #include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MAXN = 500005; // 单词数 (25w * 2)
const int MAXT = 5000005; // Trie节点数 (单词数 * 长度10)

// --- 1. Trie 树 (用于字符串 -> ID 映射) ---
int trie[MAXT][26];
int id_cnt = 0; // 当前分配到的ID
int color_id[MAXT]; // 记录Trie节点对应的颜色ID
int pos = 1; // Trie数组指针

int get_id(const string& s) {
    int p = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (!trie[p][idx]) trie[p][idx] = pos++;
        p = trie[p][idx];
    }
    if (!color_id[p]) color_id[p] = ++id_cnt; // 如果是新单词，分配新ID
    return color_id[p];
}

// --- 2. 并查集 (用于判断图是否连通) ---
int fa[MAXN];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}

// --- 全局变量 ---
int degree[MAXN]; // 记录度数

int main() {
    // 优化IO
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 初始化并查集
    for (int i = 1; i < MAXN; i++) fa[i] = i;

    string s1, s2;
    // 循环读入直到文件结束
    while (cin >> s1 >> s2) {
        int u = get_id(s1);
        int v = get_id(s2);

        degree[u]++;
        degree[v]++;
        unite(u, v); // 连接两个连通块
    }

    // 特判：如果没有木棍
    if (id_cnt == 0) {
        cout << "Possible" << endl;
        return 0;
    }

    // --- 3. 检查逻辑 ---
    
    int odd_degree_cnt = 0;
    int root_cnt = 0;
    int root_id = find(1); // 随便找个存在的点做参考根（假设id为1的点存在）
    
    // 实际上我们需要找第一个度数>0的点作为参考根，防止1号点根本没用到（虽然逻辑上按顺序分配一般会有1）
    for(int i=1; i<=id_cnt; ++i) {
        if(degree[i] > 0) {
            root_id = find(i);
            break;
        }
    }

    for (int i = 1; i <= id_cnt; i++) {
        // 忽略没有用到的点（实际上id_cnt内的都是用到的，但为了严谨判断度数>0）
        if (degree[i] == 0) continue;

        // 条件A: 奇点计数
        if (degree[i] % 2 != 0) odd_degree_cnt++;

        // 条件B: 连通性检查
        // 所有度数不为0的点，其祖宗必须相同
        if (find(i) != root_id) {
            cout << "Impossible" << endl;
            return 0; // 发现不连通，直接挂
        }
    }

    // 最终判定：奇点只能是 0 或 2
    if (odd_degree_cnt == 0 || odd_degree_cnt == 2) {
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }

    return 0;
}

记忆要点

  1. 不需要DFS：因为只问“存不存在”，不问“路径是什么”。并查集判断连通性比 DFS 跑图更快更方便。
  2. 映射转换：遇到字符串节点，第一反应 Map，如果卡时间/空间则换 Trie。这道题是 Trie 的典型应用场景。
  3. 判定公式：
  • 连通块数量 = 1
  • 奇数度点数量 = 0 或 2