pku 2513 Colored Sticks 欧拉通路问题

迷南。 2022-07-10 23:57 122阅读 0赞

这题的本质是欧拉通路的思想.

不过还需要并查集来判断是否是联通图, 用trie存储所有的字符串.

\#include <iostream> using namespace std; \#define swap(i,j) \{int temp=i; i = j; j = temp;\} struct Node \{ int index; Node\* arr\[26\]; Node() \{ index = -1; memset(arr, 0, sizeof(arr)); \} \}; int parent\[500001\]; int degree\[500001\]; Node\* root = new Node(); //根节点 int words\_count = 0; //不同的单词的总的个数 int get\_num(char\* str) \{ Node\* p = root; while(\*str) \{ int index = \*str-'a'; if(!p->arr\[index\]) p->arr\[index\] = new Node(); p = p->arr\[index\]; str++; \} if(p->index == -1) p->index = words\_count++; return p->index; \} int ufset\_find(int i) \{ int p = i; while(parent\[p\] >= 0) p = parent\[p\]; while(i != p) \{ parent\[i\] = p; i = parent\[i\]; \} return p; \} void ufset\_union(int i, int j) \{ i = ufset\_find(i); j = ufset\_find(j); if(i == j) return; if(parent\[i\] < parent\[j\]) swap(i, j); parent\[i\] += parent\[j\]; //注意这两行的先后顺序! parent\[j\] = i; \} int main() \{ memset(parent, -1, sizeof(parent)); memset(degree, 0, sizeof(degree)); char str1\[11\], str2\[11\]; while(scanf("%s %s", str1, str2) != EOF) \{ int i = get\_num(str1); int j = get\_num(str2); degree\[i\]++; degree\[j\]++; ufset\_union(i, j); \} if(!words\_count) \{ printf("Possible/n"); return 0; \} if(parent\[ufset\_find(0)\] + words\_count) \{ printf("Impossible/n"); return 0; \} int cnt = 0; for(int i = 0; i < words\_count; ++i) if(degree\[i\]&1) cnt++; if(cnt == 2 || cnt == 0) printf("Possible/n"); else printf("Impossible/n"); return 0; \}

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关图-欧拉图(欧拉环游/回路、欧拉迹/通路、Hierholzer算法、Fleury算法)

目录概念欧拉迹/通路（一笔画）半欧拉图环游欧拉环游/回路欧拉图欧拉定理推论 Hierholzer 算法作用内容时间复杂度图

以你之姓@/ 2022年12月02日 14:00/ 0 赞/ 400 阅读

相关 POJ 1386-Play on Words（有向欧拉通路）

Play on Words <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000M

迷南。/ 2022年09月25日 05:24/ 0 赞/ 113 阅读

相关欧拉通路欧拉回路的判定 Hdu 1878 欧拉回路

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路。欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路。无向图是否具有欧拉通路或回路的判定:

矫情吗；*/ 2022年08月25日 09:16/ 0 赞/ 246 阅读

相关 pku 1011 sticks 经典DFS+剪枝

以前WA过的题, 今天终于把它A了. 要从这道题目中学到发现和寻找dfs的剪枝条件: 可剪之处, 无所不在. 在注释中, 我将原棒子分的各截称之为截, 将截组合成的棒子称之

傷城~/ 2022年08月18日 03:10/ 0 赞/ 92 阅读

相关 POJ--2513 Colored Sticks

这一题本能的想法就是把所有的单词都读入，统计一下每种单词的个数，判断是否构成欧拉通路，判断图是否连通。可是可是题目给的不是数字而是单词，着我该怎么办？？？数字

港控/mmm°/ 2022年08月10日 13:48/ 0 赞/ 7 阅读

相关 pku 2513 Colored Sticks 欧拉通路问题

这题的本质是欧拉通路的思想. 不过还需要并查集来判断是否是联通图, 用trie存储所有的字符串. \include <iostream> using namespace s

迷南。/ 2022年07月10日 23:57/ 0 赞/ 123 阅读

相关 POJ 2513-Colored Sticks（连接木棍-trie树+并查集+欧拉通路）

Colored Sticks <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000

小咪咪/ 2022年06月18日 07:43/ 0 赞/ 134 阅读

相关 POJ 2513 Colored Sticks(字典树 + 并查集 + 欧拉回路)

<table> <tbody> <tr> <td> <p><strong>Colored Sticks</strong></p> <div>

浅浅的花香味﹌/ 2021年11月02日 06:32/ 0 赞/ 232 阅读

相关 poj 2513 Colored Sticks(并查集+hash+欧拉图)

<table> <tbody> <tr> <td> <p><strong>Colored Sticks</strong></p> <table>

骑猪看日落/ 2021年09月15日 18:00/ 0 赞/ 225 阅读

相关欧拉回路欧拉通路欧拉回路图

[来源][Link 1] 一、定义对于无向图：　　1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；　　2) 如果欧拉通路是回路（

灰太狼/ 2021年06月24日 15:57/ 0 赞/ 574 阅读