免费凡科网站,品牌营销全案,哪个网络公司做网站好,wordpress的选页插件比较考察技术含量的一道题。 参考链接:http://blog.csdn.net/lyy289065406/article/details/6647445 题目链接:http://poj.org/problem?id2513 首先差不多能想到这事欧拉路#xff0c;然后发现没法构图。没有尝试使用map#xff0c;刚好最近在学字典树就直接上了。 然后就是… 比较考察技术含量的一道题。 参考链接:http://blog.csdn.net/lyy289065406/article/details/6647445 题目链接:http://poj.org/problem?id2513 首先差不多能想到这事欧拉路然后发现没法构图。没有尝试使用map刚好最近在学字典树就直接上了。 然后就是并查集判断图连通。 参考链接里面的连通图判断并查集字典树映射字符串欧拉路奇数节点0个或2个 注意最后需要销毁字典树所创建的节点不然会RE 代码先字典树然后并查集然后直接主函数中判断欧拉路 1 #define _CRT_SECURE_NO_WARNINGS2 #include cstdio3 #include cstdlib4 #include cmath5 #include cstring6 #include string7 using namespace std;8 #define maxm 5000559 #define maxn 50005510 #define maxnode 3011 12 struct trie {13 trie * next[maxnode];14 int id;15 };16 trie *root;17 int totid 1;18 trie * newnode() {19 trie * t;20 t (trie*)malloc(sizeof(trie));21 t-id 0;22 for (int i 0; i maxnode; i)23 t-next[i] 0;24 return t;25 }26 void init() {27 root (trie *)malloc(sizeof(trie));28 root-id 0;29 for (int i 0; i maxnode; i)30 root-next[i] 0;31 }32 int insert_find_Str(char s[]) {33 trie *p root, *q;34 int len strlen(s), i 0;35 while (i len p-next[s[i] - a]) {36 p p-next[s[i] - a];37 i;38 }39 if (i len p-id) return p-id;40 else if (i len) return p-id totid;41 while (i len) {42 q newnode();43 p-next[s[i] - a] q;44 p p-next[s[i] - a];45 i;46 }47 p-id totid;48 return p-id;49 }50 void deltrie(trie* node) {51 while (node) {52 for (int i 0; i 26; i) {53 if ((node-next)[i])54 deltrie((node-next)[i]);55 }56 free(node);57 node 0;58 }59 }60 61 int f[maxn];62 int deg[maxn];63 char st[maxn], anost[maxn];64 65 void init_ds(int n) {66 for (int i 1; i n - 1; i)67 f[i] i;68 }69 int find(int x) {70 if (x f[x])71 return f[x];72 return f[x] find(f[x]);73 }74 void unite(int x, int y) {75 int fx find(x);76 int fy find(y);77 if (fx fy) return;78 f[fx] fy;79 }80 81 int main() {82 init();83 init_ds(maxn);84 memset(deg, 0, sizeof deg);85 while (scanf(%s, st) 0) {86 scanf(%s, anost);87 int a insert_find_Str(st);88 int b insert_find_Str(anost);89 deg[a]; deg[b];90 unite(a, b);91 }92 if (totid 1) {93 printf(Possible\n);94 return 0;95 }96 bool flag true;97 for (int i 2; i totid; i) {98 if (find(i) ! find(i - 1)) {99 flag false;
100 break;
101 }
102 }
103 if (!flag) {
104 printf(Impossible\n);
105 }
106 else {
107 int oddnum 0;
108 for (int i 1; i totid; i)
109 if (deg[i] 1) oddnum;
110 if (oddnum 0 || oddnum 2) {
111 printf(Possible\n);
112 }
113 else
114 printf(Impossible\n);
115 }
116 deltrie(root);
117 } 题目 Colored Sticks Time Limit: 5000MS Memory Limit: 128000KTotal Submissions: 37263 Accepted: 9775 Description You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color? Input Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks. Output If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible. Sample Input blue red
red violet
cyan blue
blue magenta
magenta cyanSample Output Possible Hint Huge input,scanf is recommended. 转载于:https://www.cnblogs.com/bolderic/p/6797040.html
