素材网站有哪些,织梦仿站时怎么取俩个网站的页面整合,wordpress添加豆列,遵义网站开发哪家便宜题意#xff1a;很Uva项链题目类似。 区别#xff1a; 1、字符串很多#xff0c;用map hash超时#xff0c;用Trie查找。 2、DFS判断连通#xff0c;和并查集判连通#xff0c;被我写错的地方时#xff0c;查森林的时候#xff0c;还是要Find_Set。 1 #include ios…题意很Uva项链题目类似。 区别 1、字符串很多用map hash超时用Trie查找。 2、DFS判断连通和并查集判连通被我写错的地方时查森林的时候还是要Find_Set。 1 #include iostream2 #include cstring3 #include cstdio4 #include algorithm5 6 using namespace std;7 8 const int maxnode 250000*2;9 const int sigma_size 26;10 11 struct Trie {12 int ch[maxnode][sigma_size];13 int val[maxnode];14 15 int sz;16 Trie() {sz1;memset(ch[0],0,sizeof(ch[0]));}17 int idx(char c) {return c - a;}18 19 void insert(char* s,int v) {20 int u 0,n strlen(s);21 for(int i0;in;i) {22 int c idx(s[i]);23 if(!ch[u][c]) {24 memset(ch[sz],0,sizeof(ch[sz]));25 val[sz] 0;26 ch[u][c] sz;27 }28 u ch[u][c];29 }30 val[u] v;31 }32 33 bool que(char* s) {34 int u 0,n strlen(s);35 for(int i0;in;i) {36 int c idx(s[i]);37 if(!ch[u][c])38 return false;39 u ch[u][c];40 }41 return true;42 }43 44 int values(char* s) {45 int u 0,n strlen(s);46 for(int i0;in;i) {47 int c idx(s[i]);48 u ch[u][c];49 }50 //printf(%d\n,val[u]);51 return val[u];52 53 }54 55 }sol;56 57 char str1[50],str2[50];58 59 int degree[maxnode];60 int father[maxnode];61 62 int find(int x)63 {64 if(x ! father[x])65 father[x] find(father[x]) ;66 return father[x] ;67 }68 void merge(int x,int y)69 {70 int fx find(x) ;71 int fy find(y) ;72 if(fx ! fy)73 father[fx] fy ;74 }75 76 int main()77 {78 //freopen(in.txt,r,stdin);79 int kk 0;80 81 memset(degree,0,sizeof(degree));82 83 for(int i0;imaxnode;i)84 father[i] i;85 86 87 while(scanf(%s%s,str1,str2)!EOF) {88 if(sol.que(str1)false)89 sol.insert(str1,kk);90 if(sol.que(str2)false)91 sol.insert(str2,kk);92 93 int u,v;94 u sol.values(str1);95 v sol.values(str2);96 97 //printf(%d %d\n,u,v);98 99 degree[u];
100 degree[v];
101
102 merge(u,v);
103 }
104
105 int s find(0);
106 int num 0;
107 for(int i0;ikk;i)
108 {
109 if(degree[i]%21)
110 num;
111
112 if(num2) //度数为奇数的结点数大于3欧拉路必不存在
113 {
114 coutImpossibleendl;
115 return 0;
116 }
117
118 if(find(i)!s) //存在多个祖先图为森林不连通
119 {
120 coutImpossibleendl;
121 return 0;
122 }
123 }
124
125 if(num1) //度数为奇数的结点数等于1欧拉路必不存在
126 coutImpossibleendl;
127 else //度数为奇数的结点数恰好等于2或不存在存在欧拉路
128 coutPossibleendl;
129
130 return 0;
131 } View Code 转载于:https://www.cnblogs.com/TreeDream/p/7200951.html
