[原创]POJ 2513 Colored Sticks [tire树+并查集]

2016-08-10 10:57:04 Tabris_ 阅读数：222

博客爬取于2020-06-14 22:43:57
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52169407

题目连接 : 传送阵

----------------------------------------------.
Colored Sticks
Time Limit: 5000MS Memory Limit: 128000K
Total Submissions: 35437 Accepted: 9287
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 cyan
Sample Output

Possible
Hint

Huge input,scanf is recommended.
Source

The UofA Local 2000.10.14

--------------------------------------.

题目大意 就是有多个木棍 两头有颜色 对于不同的木棍 相同颜色的一段能连接到一块 问你所有的棍能不能接成一根棍子

解题思路：
应该想到如果颜色是用数字表示的就非常好解决了 只要判断一下这些每个颜色的度就能解决 注意！！ 生成的图可能是个森林 所以要用并查集判断下 是否生成的是一个树（应该是环）
现在想的问题就只剩下字符串怎么转化成数字了 用map转化的话不可行 所以想到用tire树来解决 这样才不会爆内存
对于学会tire树的你相信不是个问题 注意的是 把每个串插入到树中的时候只要把最后一个字符所在的节点+1 就行了 再在tire中加上一个index（索引）的元素 记录这个串的编号 (查询操作是没用的)
刚学字符串10days 纯属个人解法 如有错误 请一定要指正

附本题代码
---------------------------------------------.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
# include <bits/stdc++.h>
using namespace std;

# define LL long long int
# define lalal puts("********");

const int N = 1010101;
const int Max = 26;
char s1[11],s2[11];
int pre[505050];
int degree[505050];
typedef struct node
{
    struct node *next[Max];
    int num;
    int index;
} Node;

//创建一个新节点
Node *createNew()
{
    Node *p=new Node;
    for(int i=0; i<Max; i++)
        p->next[i]=NULL;

    p->num=0;
    return p;
}

Node *head;
int ind=0;
//插入一个字符串
Node *Insert_str(char str[])
{
    int len=strlen(str);
    //  printf("len = %d--  ",len);
    Node *t,*p=head;
    for(int i=0; i<len; i++)
    {
        int c=str[i]-'a';
        if( p->next[c] == NULL )
        {
            //lalal
            t=createNew();
            p->next[c]=t;
        }
        p=p->next[c];
        //统计的时候要分清时机
        // cout<<p->num<<"-"<<str[i]<<" ";
    }
    p->num++;
    if(p->num==1)  p->index=++ind;
    return p;
}
int findi(int x)
{
    int r=x;
    while(r!=pre[r])
        r=pre[r];

    int i=x,j;
    while(i!=j)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y)
{
    int fx=findi(x),fy=findi(y);
    if(fx!=fy)
        pre[fx]=fy;
}

void init()
{
    for(int i=0; i<=500050; i++)
    {
        pre[i]=i;
        degree[i]=0;
    }
    return ;
}

int main()
{
    head = createNew();
    init();
    int num=0;
    Node * tem1,*tem2 ;
    while(~scanf("%s %s",s1,s2))
    {
        tem1 = Insert_str(s1);
        tem2 = Insert_str(s1);

        degree[tem1->index]++;
        degree[tem2->index]++;

        join(tem1->index,tem2->index);
    }

    for(int i=1; i<=ind; i++)
    {
        if(degree[i]%2 == 1) num++;

        if(num>=3)
        {
            puts("Impossible");
            break;
        }

        if(findi(1)!=findi(i))
        {
            puts("Impossible");
            break;
        }

    }

    if(num!=1) puts("Possible");
    else     puts("Impossible");

    return 0;

}