python/TangDou/AcWing/EulerPath/POJ2513.md

POJ 2513 Colored Sticks

一、题目描述

一堆木棍左右两端涂有颜色,相同颜色的可以连接在一起，问所有木棍能否都连上

二、字符串HASH+并查集

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

const int N = 250010 << 1;
int p[N]; // 并查集
int d[N]; // 度

/*
在这个代码中，我们定义了一个函数getHash来获取字符串的哈希值。
这个函数使用了一种称为多项式滚动哈希的方法，它将字符串看作一个31进制的数，并将每个字符的ASCII值减去'a'的ASCII值
加1作为该字符的值。然后，我们将每个字符的值乘以31的相应次方，并将结果加到哈希值上。
为了防止哈希值溢出，我们在每一步都对哈希值取模N。
*/
int getHash(string s) {
    int p = 31, b = 1, hash = 0;
    for (int i = 0; i < s.size(); i++) {
        hash = (hash + (s[i] - 'a' + 1) * b) % N;
        b = (b * p) % N;
    }
    return hash;
}

// 并查集
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

char str1[15], str2[15]; // 两个字符串
int b[N];                // 判断某个字符串HASH值是不是已经出现过的桶

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ2513.in", "r", stdin);
#endif
    // 初始化并查集
    for (int i = 0; i < N; i++) p[i] = i;
    // 离散化后的节点编号，是不是存在一笔画的标识
    int id = 0, flag = 1;

    while (~scanf("%s%s", str1, str2)) {
        int s1 = getHash(str1), s2 = getHash(str2); // 计算出个字符串的HASH值，而且，数值在N以下，这样才能用桶
        if (!b[s1]) b[s1] = ++id;                   // 给字符串编号，去重
        if (!b[s2]) b[s2] = ++id;                   // 给字符串编号，去重
        int x = b[s1], y = b[s2];                   // 去重+映射后的字符串编号
        d[x]++, d[y]++;                             // 记录度
        // 合并并查集
        if (find(x) != find(y)) p[find(x)] = find(y); // 辅助校验图是否是连通的
    }

    int odd = 0, cnt = 0;
    for (int i = 1; i <= id; i++) { // 枚举每个去重后的字符串
        if (p[i] == i) cnt++;       // 连通块个数
        if (d[i] % 2) odd++;        // 奇数度节点个数
    }

    // 如果奇数度个数不是0，而且，还不是2，那肯定不是一笔画
    // 如果连通块个数不是1，也不能一笔画
    if ((odd != 0 && odd != 2) || cnt != 1) flag = 0;
    // 空数据也需要处理，这太BT了！
    if (id == 0) flag = 1;

    if (flag)
        puts("Possible");
    else
        puts("Impossible");
    return 0;
}

三、AcWing版本的字符串Hash

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
typedef unsigned long long ULL;
const int N = 250010 << 1;
int p[N];
int d[N];

ULL getHash(string s) {
    int P = 131, b = 1;
    ULL hash = 0;
    for (int i = 0; i < s.size(); i++) {
        hash = hash + s[i] * b;
        b = b * P;
    }
    return hash;
}

int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

char str1[15], str2[15];
int b[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ2513.in", "r", stdin);
#endif

    for (int i = 0; i < N; i++) p[i] = i;

    int id = 0, flag = 1;

    while (~scanf("%s%s", str1, str2)) {
        int s1 = getHash(str1) % N, s2 = getHash(str2) % N;
        if (!b[s1]) b[s1] = ++id;
        if (!b[s2]) b[s2] = ++id;
        int x = b[s1], y = b[s2];
        d[x]++, d[y]++;

        if (find(x) != find(y)) p[find(x)] = find(y);
    }

    int odd = 0, cnt = 0;
    for (int i = 1; i <= id; i++) {
        if (p[i] == i) cnt++;
        if (d[i] % 2) odd++;
    }

    if ((odd != 0 && odd != 2) || cnt != 1) flag = 0;

    if (id == 0) flag = 1;

    if (flag)
        puts("Possible");
    else
        puts("Impossible");
    return 0;
}

四、Trie+并查集

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

using namespace std;
const int N = 500010;

int p[N];                // 并查集数组
int d[N];                // 度
char str1[15], str2[15]; // 两个字符串
// int b[N];                // 记录字符串(对应的HASH值)是否出现过，是桶的概念
int id[N], n;  // 用于离散化，根据p是否出现，决定是否为其分配新的节点编号，有旧的使旧的，有新的创建后使新的
int idx;       // 创建Trie树时的游标
int tr[N][26]; // Trie树

/*
如果平均字符串长度是10，那么在最坏的情况下，Trie树中最多可能有500000 * 10 = 5000000个节点。
这是因为在最坏的情况下，每个字符串都不共享任何前缀，因此每个字符串的每个字符都会在Trie树中创建一个新的节点。
需要注意的是，这是一个上界，实际的节点数量可能会少于这个值，因为许多字符串可能会共享一些前缀，这些前缀在Trie树中只会被存储一次。
*/
int insert(string str) { // 插入字典树并返回结尾字符节点编号
    int p = 0;
    for (int i = 0; i < str.size(); i++) {
        int u = str[i] - 'a'; // 映射成0~25,本题只有小写字母
        if (!tr[p][u]) tr[p][u] = ++idx;
        p = tr[p][u];
    }
    /* 如上面的论述结果，idx:Trie树中有很多的节点,可每个字符串最后的终点只有1个
       我们需要知道我们在心中创建的图有多少个节点，一般用n表示，如果我们直接使用Trie树中的p,虽然在数据范围内不会越界，但在1~p之间，肯定存在无效的节点，这是我们不能接受的，
       办法就是直接离散化，只保留有用的节点，重新编号:id[N]+cnt
    */
    if (!id[p]) id[p] = ++n; // 节点编号
    return id[p];
}

// 并查集
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ2513.in", "r", stdin);
#endif
    for (int i = 0; i < N; i++) p[i] = i;

    while (~scanf("%s%s", str1, str2)) {
        int a = insert(str1), b = insert(str2); // 利用Trie树找出字符串的HASH值,其它与纯字符串131进制的代码一致
        d[a]++, d[b]++;
        if (find(a) != find(b)) p[find(a)] = find(b);
    }

    int odd = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) cnt++;
        if (d[i] % 2) odd++;
    }
    int flag = 1;
    if ((odd != 0 && odd != 2) || cnt != 1) flag = 0;

    if (n == 0) flag = 1;

    if (flag)
        puts("Possible");
    else
        puts("Impossible");
    return 0;
}

五、STL \ map+vector

#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 500010;
char s1[15], s2[15]; // 两个字符串

// POJ只能使用map, 不能使用unordered_map,而map性能很差，代码非常可能TLE，我尝试修改为链式前向星，结果TLE了
map<string, int> _map;
vector<int> g[N];
int id, st[N], d[N];

int cnt;
void dfs(int u) {
    cnt++;
    st[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (st[v]) continue;
        dfs(v);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ2513.in", "r", stdin);
#endif

    while (~scanf("%s%s", s1, s2)) {
        int a, b;
        if (!_map[s1]) _map[s1] = ++id; // 手动离散化，帅！
        if (!_map[s2]) _map[s2] = ++id;
        a = _map[s1], b = _map[s2];
        // 邻接表走起
        g[a].push_back(b), g[b].push_back(a);
        // 记录度
        d[a]++, d[b]++;
    }
    // 大家小心，这题有空数据的情况，应输出possible！
    if (id == 0) {
        puts("Possible");
        return 0;
    }

    dfs(1); // 判断有没有孤立点
    if (cnt != id) {
        puts("Impossible");
        return 0;
    }

    cnt = 0;
    for (int i = 1; i <= id; i++) // 无向图有0个或两个奇度点含有
        if (d[i] % 2) cnt++;      // 欧拉回路或欧拉通路

    if (cnt == 0 || cnt == 2) // 好像有点卡常，交c++冲过去了...
        puts("Possible");
    else
        puts("Impossible");
    return 0;
}