网站名称去哪里注册,pc端网站转手机站怎么做,网络推广方法有哪几种,做网站的图片素材网站有哪些/*思路#xff1a;类似图论中“一笔画”问题#xff0c;两根木棒的相连接的端点是一样的颜色#xff0c;#xff08;a,b#xff09;--(b,c)--(c, d)....方法#xff1a;trie树并查集#xff0c; 利用trie树建立字符串和某一个节点的映射#xff0c;并将这些和字符串构成… /*思路类似图论中“一笔画”问题两根木棒的相连接的端点是一样的颜色a,b--(b,c)--(c, d)....方法trie树并查集 利用trie树建立字符串和某一个节点的映射并将这些和字符串构成映射的节点建成图 用并查集判断图的连通*/ 1 #includeiostream 2 #includecstdio3 #includecstring4 #define N 2500005*25 using namespace std;6 int f[N];7 int indgr[N];8 int trie[N][26];9 int nodeNum, pre, cnt, oddDgr, root;
10 int getFather(int x)//并查集寻找父亲节点压缩路径
11 {
12 return x f[x] ? x : f[x]getFather(f[x]);
13 }
14
15 void Union(int a, int b)//并查集的合并
16 {
17 int fagetFather(a), fbgetFather(b);
18 if(fa!fb)
19 f[fa]fb;
20 }
21
22 int main()
23 {
24 char color[15];
25 int i;
26 for(i0; iN; i)
27 f[i]i;
28 while(scanf(%s, color)!EOF)
29 {
30 cnt;
31 int cur0, Lstrlen(color);
32 for(i0; iL; i)
33 {
34 int kcolor[i]-a;
35 if(!trie[cur][k])
36 trie[cur][k]nodeNum;
37 curtrie[cur][k];
38 }
39 indgr[cur];
40 if(cnt%2) precur;
41 else
42 Union(pre, cur);
43 }
44 for(i0; inodeNum; i)
45 {
46 if(indgr[i]1) oddDgr;
47 if(indgr[i] f[i]i) root;
48 if(oddDgr2 || root1) break;
49 }
50 if((oddDgr0 || oddDgr2) root1 || oddDgr0 root0)//注意空树的情况下是输出Impossible, 开始就是错在了这里
51 printf(Possible\n);
52 else printf(Impossible\n);
53 return 0;
54 }转载于:https://www.cnblogs.com/hujunzheng/p/3775673.html
