POJ 2513-Colored Sticks（连接木棍-trie树+并查集+欧拉通路）

小咪咪 2022-06-18 07:43 110阅读 0赞

Colored Sticks

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;128000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;37049</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;9729</td> 
  </tr> 
 </tbody> 
</table>

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][]

## 题目意思： ##

有一堆木棍， 木棍的两个端点用一些不同的颜色着色， 将它们在端点处连接起来，要求端点的颜色相同，判断是否能够实现。

##    解题思路： ##

啊(○´･д･)ﾉ本来以为要用这么多知识点就很困难，结果好像…(⊙v⊙)嗯直接用欧拉回路判断的充要条件还是很简单的。

将不同的颜色视为图的节点，木棍本身视为边，建图。

数据量巨大，map妥妥超时，用trie树保存记录不同颜色的序号，并查集判断是否只有一个父节点（这种情况下图才是连通的），若满足题设条件，则图中必然存在欧拉通路。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iomanip>
    #include<cstdlib>
    #include<iostream>
    #include<queue>
    #include<algorithm>
    using namespace std;
    #define MAXN 510010
    #define INF 0x3f3f3f3f
    int trie[MAXN][26];//字典树
    int num[MAXN][26];//颜色的序号
    int degree[MAXN],fa[MAXN];//颜色出现的次数、并查集
    int n,e;//树的数目和序号
    //字典树
    int Insert(char s[])
    {
        int j=0;
        int len=strlen(s);
        for(int i=0; i<len; i++)
            if(trie[j][s[i]-'a']) j=trie[j][s[i]-'a'];
            else
            {
                trie[j][s[i]-'a']=++e;
                j=trie[j][s[i]-'a'];
            }
        if (num[j][s[len-1]-'a']==0) //当前字母没有出现过
            num[j][s[len-1]-'a']=++n;
        return num[j][s[len-1]-'a'];//颜色的序号
    }
    //并查集
    int Find(int x)
    {
        if(x!=fa[x]) fa[x]=Find(fa[x]);
        return fa[x];
    }
    void Join(int i,int j)
    {
        int p=Find(i);
        int q=Find(j);
        if(p!=q) fa[p]=q;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
    //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
         n=e=0;
        memset(trie,0,sizeof(trie));
        memset(num,0,sizeof(num));
        memset(degree,0,sizeof(degree));
        for(int i=1; i<MAXN; i++)
            fa[i]=i;
        char s1[11],s2[11];
        while(cin>>s1>>s2)
        {
            int p=Insert(s1),q=Insert(s2);//插入字典树，得到颜色的序号
            ++degree[p],++degree[q];//更新度数
            Join(p,q);
        }
        int cnt=0;//父节点的个数
        for(int i=1; i<=n; i++)//是否只有一个父节点
        {
            if(i==Find(i)) ++cnt;
            if (cnt>1) break;
        }
        if (cnt>1) cout<<"Impossible"<<endl;//只有一个父节点时是不连通的
        else
        {
            int sum=0;
            for(int i=1; i<=n; i++)
                if (degree[i]%2) ++sum;//统计度为奇数的点的个数
            if(sum==0||sum==2) cout<<"Possible"<<endl;//无向图欧拉回路中度为奇数的点的个数是0/2
            else cout<<"Impossible"<<endl;
        }
    }

[The UofA Local 2000.10.14]: http://poj.org/searchproblem?field=source&key=The+UofA+Local+2000.10.14