点击打开POJ题目连接

题意:给定一些木棍,每根木棍两头都有两个颜色,相同颜色的木棍头可以连接,问你这些木棍能否最后连接成一条链。

分析:题目数据量很大,需要用到字典树或者哈希得到每个字符串的id,然后用并查集判断是否能够只连接成一条链,最后判断是否符合奇数个颜色的个数不超过两个即可。

字典树C++代码:

#pragma GCC push_options
#pragma GCC optimize("O3")
#pragma loop_opt(on)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int maxnode = 555555, sigmsSize = 26;
int colorcnt, pa[maxnode], cnt[maxnode];
int Find(int x) { return pa[x] == x ? x : pa[x] = Find(pa[x]); }

struct Tire{
    int ch[maxnode][sigmsSize];
    int val[maxnode], sz;
    Tire() { sz = 1; memset(ch, 0, sizeof(ch)); };
    int insert(const char *s) {
        int u = 0, len = strlen(s);
        for(int i = 0; i < len; ++i) {
            int c = s[i] - 'a';
            if(!ch[u]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u] = sz++;
            }
            u = ch[u];
        }
        if(!val[u]) val[u] = ++colorcnt;
        return val[u];
    }
}tire;

char s1[15], s2[15];

int main() {
    for(int i = 0; i < maxnode; ++i)
        pa[i] = i;
    while(~scanf("%s %s", s1, s2)) {
        int a = tire.insert(s1), b = tire.insert(s2);
        ++cnt[a], ++cnt[b];
        pa[Find(a)] = Find(b);
        // printf("%d %d--\n", a, b);
    }
    int f = Find(1), odd = 0;
    for(int i = 2; i <= colorcnt; ++i)
        if(Find(i) != f) {
            puts("Impossible");
            return 0;
        }
    for(int i = 1; i <= colorcnt; ++i)
        if(cnt[i] % 2)
            ++odd;
    if(odd <= 2) puts("Possible");
    else puts("Impossible");
    return 0;
}

哈希C++代码:

#pragma GCC push_options
#pragma GCC optimize("O3")
#pragma loop_opt(on)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int maxnode = 1000007, sigmsSize = 26;
int pa[maxnode], cnt[maxnode];
int Find(int x) { return pa[x] == x ? x : pa[x] = Find(pa[x]); }
char s1[15], s2[15];

int getHash(const char *s) {
    int ha = 1, len = strlen(s);
    for(int i = 0; i < len; ++i)
        ha = (ha * 37 + s[i] - 'a') % maxnode;
    return ha;
}

int main() {
    for(int i = 0; i < maxnode; ++i)
        pa[i] = i;
    while(~scanf("%s %s", s1, s2)) {
        int a = getHash(s1), b = getHash(s2);
        ++cnt[a], ++cnt[b];
        pa[Find(a)] = Find(b);
    }
    int odd = 0;
    for(int i = 0; i < maxnode; ++i)
        if(cnt[i] && Find(i) == i)
            ++odd;
    if(odd > 1) {
        puts("Impossible");
        return 0;
    }
    odd = 0;
    for(int i = 0; i < maxnode; ++i)
        if(cnt[i] % 2)
            ++odd;
    if(odd <= 2) puts("Possible");
    else puts("Impossible");
    return 0;
}

欢迎留言