poj 2513 Colored Sticks (欧拉回路+并查集+Hash)

现在的位置: 首页 > 算法 > 正文

RSS

上篇下篇

poj 2513 Colored Sticks (欧拉回路+并查集+Hash)

2018年09月22日 ⁄ 算法 ⁄ 共 1573字 ⁄ 字号小中大 ⁄ 评论关闭

题目链接：http://poj.org/problem?id=2513

题目大意：给出无数根筷子，每个筷子头尾各一个单词代表颜色

颜色相同则可以拼在一起

如 blue red 的筷子和 red violet 的筷子可以拼在一起

如 red blue 的筷子和 red violet 的筷子也可以拼在一起

筷子不分头尾，可以任意调换

问所有的筷子能否拼成一条线？

解题思路：把每个单词看成一个点，每根筷子就代表一条边！

这样就能得到一个图

所有筷子连成一条线，换句话说就是一次遍历所有的边

然后可以转化成"一笔连成"的问题，无向图的欧拉通路！

奇数度顶点的数量0或2时，欧拉通路成立

先判断这个图是不是连通图(并集合)

边数太多，输入的时候如果用strcmp判断是哪个点会TLE

我们可以用Hash来处理

代码:

//BKDRHash + 欧拉回路 + 并查集
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 251000
int parent[MAX]={0},v[MAX]={0};
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    
    return (hash & 0x7FFFFFFF)%MAX;
}


void Empty() //初始化parent[]
{
    int i;
    for(i=0;i<MAX;i++)
        parent[i]=i;
}

int Find(int x)  //并查集 Find()
{
    int s,j;
    s=x;
    while(x!=parent[x])
    {
        x=parent[x];
    }
    while(s!=x)
    {
        j=parent[s];
        parent[s]=x;
        s=j;
    }
    return x;
}

void Union(int r1,int r2)   //并查集 Union()
{
    int R1,R2;
    R1=Find(r1);
    R2=Find(r2);
    if(R1!=R2)
    {
        parent[R1]=R2;
    }
}

int main()
{
    char a[11],b[11];
    int i,pd,js,atemp,btemp,tempx;
    Empty();  //别忘记初始化了！
    while(scanf("%s%s",a,b)!=EOF)
    {
        atemp=BKDRHash(a);   //返回 哈希值
        btemp=BKDRHash(b);   //返回 哈希值
        v[atemp]++;      //顶点的度++
        v[btemp]++;      //顶点的度++
        if(Find(atemp)!=Find(btemp))
        {
            Union(atemp,btemp);
        }
        
    }
    for(i=0,js=0;i<MAX;i++)
    {
        if(v[i]>0&&v[i]%2!=0)
            js++;    //顶点的度为奇数的数目
    }
    if(js!=0&&js!=2)
    {
        printf("Impossible\n");
        return 0;
    }
    for(i=0,tempx=-1,pd=1;i<MAX;i++)
    {
        if(v[i]>0)
        {
            if(tempx==-1)
            {
                tempx=Find(i);   //**寻找祖先,是Find()
            }
            else if(tempx!=Find(i))   //**祖先不同 就不符合,不是连通图
            {
                pd=0;
                printf("Impossible\n");
                return 0;
            }
        }
    }
    printf("Possible\n");
    return 0;
}

注：原创文章，转载请注明出处