POJ 3630 Phone List_专业打酱油_百度空间
一个字典树的题。如果一个节点是Ending而他还有子节点的话那就NO掉,否则就YES。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <memory.h>

using namespace std;

#define NR_CHILDS 10
#define NR_NODES 100000

struct trie_node_t {
trie_node_t * childs[10];
bool is_ending;
};

trie_node_t nodes[NR_NODES];
trie_node_t *trie_root, *node_ending;

void
init_trie(void)
{
memset(nodes, 0, sizeof(nodes));
trie_root = nodes;
node_ending = trie_root + 1;

return;
}

bool
confict_exists(trie_node_t *root_node)
{
bool parent_ending(root_node->is_ending);

for (trie_node_t **iter = root_node->childs, **iter_end = root_node->childs + NR_CHILDS; iter != iter_end; ++iter) {
if (*iter) {
if (parent_ending) {
return true;
}
if (confict_exists(*iter)) {
return true;
}
}
}

return false;
}

void
add_string(char* str)
{
trie_node_t *cur(trie_root);
int c;

--str;

while (*++str) {
if (!cur->childs[c = *str - '0']) {
cur->childs[c] = node_ending++;
}
cur = cur->childs[c];
}

cur->is_ending = true;

return;
}

void
solve_prob(void)
{
int nr_number;
char number[11];

init_trie();

cin >> nr_number;
while (nr_number--) {
cin >> number;
add_string(number);
}

cout << (confict_exists(trie_root) ? "NO" : "YES") << endl;

return;
}

int
main(void)
{
int nr_cases;

ios::sync_with_stdio(false);

//freopen("test.txt", "r", stdin);

cin >> nr_cases;
while (nr_cases--) {
solve_prob();
}

return 0;
}


郑重声明:资讯 【POJ 3630 Phone List_专业打酱油_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——