首页 > 代码库 > POJ2513-Colored Sticks

POJ2513-Colored Sticks

2024-07-07 13:10:44   231人阅读

+ View Code?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*<br>思路：类似图论中“一笔画”问题，两根木棒的相连接的端点是一样的颜色，（a,b）--(b,c)--(c, d)....<br>方法：trie树+并查集， 利用trie树建立字符串和某一个节点的映射，并将这些和字符串构成映射的节点建成图， 用并查集判断图的连通<br>*/<br> 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define N 2500005*2
 5 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 fa=getFather(a), fb=getFather(b);
18     if(fa!=fb)
19        f[fa]=fb;
20 }
21
22 int main()
23 {
24    char color[15];
25    int i;
26    for(i=0; i<N; ++i)
27    f[i]=i;
28    while(scanf("%s", color)!=EOF)
29   {
30      cnt++;
31      int cur=0, L=strlen(color);
32      for(i=0; i<L; ++i)
33      {
34         int k=color[i]-‘a‘;
35   　　　 if(!trie[cur][k])
36            trie[cur][k]=++nodeNum;
37　　　    cur=trie[cur][k];
38      }
39 　　　++indgr[cur];
40      if(cnt%2) pre=cur;
41      else
42 　　　　Union(pre, cur);
43 　}
44   for(i=0; i<=nodeNum; ++i)
45   {
46     if(indgr[i]&1) ++oddDgr;
47     if(indgr[i] && f[i]==i) ++root;
48     if(oddDgr>2 || root>1) break;
49   }
50   if((oddDgr==0 || oddDgr==2) && root==1 || oddDgr==0 && root==0)//注意空树的情况下是输出Impossible, 开始就是错在了这里
51   printf("Possible\n");
52   else printf("Impossible\n");
53   return 0;
54 }

　　


联系
我们