poj 2513 Colored Sticks(欧拉回路 并查集 路径压缩 字典树)(困难)

Colored Sticks

Time Limit: 5000MS   Memory Limit: 128000K
Total Submissions: 32545   Accepted: 8585

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

题意:

给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的。

思路:

这题不错,用到了三个知识点,我开始没用字典树,超时了。顺便学习了字典树。

看到了一个不错的题解。

可以用图论中欧拉路的知识来解这道题,首先可以把木棒两端看成节点,把木棒看成边,这样相同的颜色就是同一个节点

问题便转化为:

给定一个图,是否存在“一笔画”经过涂中每一点,以及经过每一边一次。

这样就是求图中是否存在欧拉路Euler-Path

回顾经典的“七桥问题”,相信很多同学马上就明白了什么是 欧拉路 了,这里不多作解释。

由图论知识可以知道,无向图存在欧拉路的充要条件为:

①     图是连通的;

②     所有节点的度为偶数,或者有且只有两个度为奇数的节点。

其中①图的连通性用程序判断比较麻烦,先放一下。

这里先说说②关于度数的判断方法:


Blue


Magenta


Violet


Cyan


Red

节点的度用颜色出现次数来统计,如样例中,蓝色blue出现三次(不管是出度还是入度),那么blue结点的度就为3,同样地,我们也可以通过输入得到其他全部结点的度,于是,我们有:

Blue=3

Red=2

Violet=1

Cyan=2

Magenta=2

用一个一维数组就能记录了,然后分别 模2,就能判断颜色结点的奇偶性

只要奇度数的结点数的个数 = 1 或 >=3 ,即使①图连通,欧拉路也必不存在

但是若 奇度数的结点数的个数 为0或 ==2,那么我们继续进行①图的连通性证明:

证明①图的连通性,使用并查集MergeSet是非常高效的方法。

基本方法:

初始化所输入的n个结点为n棵树,那么就有一个n棵树的森林,此时每棵树的有唯一的结点(根),该结点的祖先就是它本身。再通过不断地输入边,得到某两个结点(集合)之间的关系,进而合并这两个结点(集合),那么这两个集合就构成一个新的集合,集合内的所有结点都有一个共同的新祖先,就是这个集合(树)的根。

最后只要枚举任意一个结点,他们都具有相同的祖先,那么就能证明图时连通的了。

但是单纯使用并查集是会超时的,因为这样会导致每次寻找某个结点的祖先时,平均都会花费O(n/2)时间,最坏情况,当n==50W时,O(n/2)大概为25ms,那么要确定50W个结点是否有共同祖先时,总费时为50W*25ms ,铁定超,不算了= =

因此必须使用并查集时必须压缩路径,前几次搜索某个结点k的祖先时,在不断通过父亲结点寻找祖先结点时,顺便把从k到最终祖先结点S中经过的所有结点的祖先都指向S,那么以后的搜索就能把时间降低到O(1)

由于并查集必须利用 数组的下标 与 存储的对象,使用int是比较方便的处理方法,但是题目的“颜色结点”是string,不方便用来使用并查集,即使用map也不行,虽然STL的map是基于hash的基础上,但并不高效,在本题中使用会超时。

为此可以使用Trie字典树,得到每个颜色单词对应的int编号id ,可以说利用Trie把string一一映射到int,是本题后续处理的关键所在。关于动态创建字典树的方法去百度,这里不多说,下面只用用一个图简单说明一下用Trie字典树标识第一个颜色单词blue:

这个题目涉及了多个基本数据结构和算法,综合性很强,非常有代表性,能够A到这题确实是受益良多。

知识考查点:

1、字典树;

2、欧拉路:其中又考察了判断是否为连通图;

3、并查集 及其优化方法(路径压缩)。

输出:

POSSIBLE:  奇度数结点个数==0 或 ==2  且  图连通

IMPOSSIBLE:奇度数结点个数==1 或 >=3  或  图不连通

PS:注意创建TrieTree链表时,C++不存在NULL,要用 0 替代 NULL

代码:

//超时的

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxx 250000
struct edge
{
    int u,v;
}e[maxx];
char color1[15],color2[15];
int in[maxx],out[maxx],bused[maxx];
char col[maxx][12];
int pre[maxx];
int num,sum;

int turn(char *s)
{
    int i;
    for(i=0;i<sum;i++)
    {
        if(strcmp(col[i],s)==0)
            return i;
    }
    if(i==sum)
    {
        strcpy(col[sum],s);
        sum++;
        return sum-1;
    }
}

int Find(int x)
{
    int s;
    for(s=x;pre[s]>=0;s=pre[s]);
    while(s!=x)
    {
        int tmp=pre[x];
        pre[x]=s;
        x=tmp;
    }
    return s;
}

void Union(int R1,int R2)
{
    int r1=Find(R1),r2=Find(R2);
    int tmp=pre[r1]+pre[r2];
    if(pre[r1]>pre[r2])
    {
        pre[r1]=r2;
        pre[r2]=tmp;
    }
    else
    {
        pre[r2]=r1;
        pre[r1]=tmp;
    }
}

int connect()
{
    int u,v;
    for(int i=0;i<sum;i++)
        pre[i]=-1;
    for(int i=0;i<num;i++)
    {
        u=e[i].u,v=e[i].v;
        if(u!=v && Find(u)!=Find(v))
            Union(u,v);
    }
    int first=-1,i;
    for(i=0;i<sum;i++)
    {
        if(!bused[i]) continue;
        if(first==-1) first=i;
        else if(Find(i)!=Find(first)) break;
    }
    if(i<sum)
        return 0;
    else
        return 1;
}

int main()
{
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    memset(bused,0,sizeof(bused));
    num=0;sum=0;
    scanf("%s%s",color1,color2);
    strcpy(col[0],color1);
    strcpy(col[1],color2);
    sum=2;
    e[0].u=0,e[0].v=1;
    out[0]++;in[1]++;
    bused[0]=bused[1]=1;
    num=1;
    int qq=1;
    while(scanf("%s%s",color1,color2)!=EOF)
    {
        int u=turn(color1),v=turn(color2);
        e[num].u=u,e[num].v=v;
        out[u]++;in[v]++;
        bused[u]=bused[v]=1;
        num++;qq++;
        if(qq==5)
            break;
    }

    for(int i=0;i<num;i++)
        cout<<e[i].u<<" "<<e[i].v<<endl;

    for(int i=0;i<sum;i++)
        cout<<i<<" in:"<<in[i]<<"  out:"<<out[i]<<endl;

    cout<<"点:"<<sum<<" "<<"边:"<<num<<endl;
    int flag=1;
    int one=0,none=0;
    for(int i=0;i<sum;i++)
    {
        if(!bused[i])continue;
        if(out[i]-in[i]>=2||in[i]-out[i]>=2){flag=0;break;}
        if(out[i]==0&&in[i]==0){flag=0;break;}
        if(out[i]-in[i]==1)
        {
            one++;
            if(one>1){flag=0;break;}
        }
        if(in[i]-out[i]==1)
        {
            none++;
            if(none>1){flag=0;break;}
        }

    }
    if(one!=none) flag=0;
    if(!connect()) flag=0;
    if(flag)
        printf("Possible\n");
    else
        printf("Impossible\n");
    return 0;
}

用了字典树:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
//79372K 1157MS
//trie+并查集+欧拉路径
const int maxnum=500010;
int degree[maxnum],parent[maxnum],rank[maxnum];
int n=1;
struct node
{
    int id;
    bool use;
    node *next[27];
    node()
    {
        id=0;
        use=false;
        int i;
        for(i=0;i<27;i++)
            next[i]=NULL;
    }
};
node *root;

int hash(char *str)
{
    node *p=root;
    int k;
    while(*str!=0)
    {
        k=*str-'a';
        if(p->next[k]==NULL)
            p->next[k]=new node();
        p=p->next[k];
        str++;
    }
    if(!p->use)
    {
        p->id=n;
        n++;
        p->use=true;
        return p->id;
    }
    else
        return p->id;
}

int find(int u)
{
    if(u!=parent[u])
        parent[u]=find(parent[u]);
    return parent[u];
}

void Union(int i,int j)
{
    if(rank[i]<rank[j])
        parent[i]=j;
    else
    {
        parent[j]=i;
        if(rank[i]==rank[j])
            i++;
    }
}

int main()
{
    char a[15],b[15];
    int i;
    root=new node();
    for(i=1;i<maxnum;i++)
        parent[i]=i;
    while(scanf("%s%s",a,b)!=EOF)
    {
        int k=hash(a);
        int l=hash(b);
        degree[k]++;
        degree[l]++;

        int p=find(k);
        int q=find(l);
        if(p!=q)
            Union(p,q);
    }
    int t=find(1);
    int num=0;  //度数为奇数的结点个数
    for(i=1;i<n;i++)
    {
        if(find(i)!=t)//存在多个祖先,图为森林,不连通
        {
            printf("Impossible\n");
            return 0;
        }
        if(degree[i]%2==1)
            num++;
        if(num>2)  //度数为奇数的结点数大于3,欧拉路必不存在
        {
            printf("Impossible\n");
            return 0;
        }
    }
    if(num==1)  //度数为奇数的结点数等于1,欧拉路必不存在
        printf("Impossible\n");
    else   //度数为奇数的结点数恰好等于2或不存在,存在欧拉路
        printf("Possible\n");
    return 0;
}

用一个一维数组就能记录了,然后分别 模2,就能判断颜色结点的奇偶性

只要奇度数的结点数的个数 = 1 或 >=3 ,即使①图连通,欧拉路也必不存在

但是若 奇度数的结点数的个数 为0或 ==2,那么我们继续进行①图的连通性证明:

证明①图的连通性,使用并查集MergeSet是非常高效的方法。

基本方法:

初始化所输入的n个结点为n棵树,那么就有一个n棵树的森林,此时每棵树的有唯一的结点(根),该结点的祖先就是它本身。再通过不断地输入边,得到某两个结点(集合)之间的关系,进而合并这两个结点(集合),那么这两个集合就构成一个新的集合,集合内的所有结点都有一个共同的新祖先,就是这个集合(树)的根。

最后只要枚举任意一个结点,他们都具有相同的祖先,那么就能证明图时连通的了。

但是单纯使用并查集是会超时的,因为这样会导致每次寻找某个结点的祖先时,平均都会花费O(n/2)时间,最坏情况,当n==50W时,O(n/2)大概为25ms,那么要确定50W个结点是否有共同祖先时,总费时为50W*25ms ,铁定超,不算了= =

因此必须使用并查集时必须压缩路径,前几次搜索某个结点k的祖先时,在不断通过父亲结点寻找祖先结点时,顺便把从k到最终祖先结点S中经过的所有结点的祖先都指向S,那么以后的搜索就能把时间降低到O(1)

由于并查集必须利用 数组的下标 与 存储的对象,使用int是比较方便的处理方法,但是题目的“颜色结点”是string,不方便用来使用并查集,即使用map也不行,虽然STL的map是基于hash的基础上,但并不高效,在本题中使用会超时。

为此可以使用Trie字典树,得到每个颜色单词对应的int编号id ,可以说利用Trie把string一一映射到int,是本题后续处理的关键所在。关于动态创建字典树的方法去百度,这里不多说,下面只用用一个图简单说明一下用Trie字典树标识第一个颜色单词blue:

这个题目涉及了多个基本数据结构和算法,综合性很强,非常有代表性,能够A到这题确实是受益良多。

知识考查点:

1、字典树;

2、欧拉路:其中又考察了判断是否为连通图;

3、并查集 及其优化方法(路径压缩)。

输出:

POSSIBLE:  奇度数结点个数==0 或 ==2  且  图连通

IMPOSSIBLE:奇度数结点个数==1 或 >=3  或  图不连通

PS:注意创建TrieTree链表时,C++不存在NULL,要用 0 替代 NULL

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-06

poj 2513 Colored Sticks(欧拉回路 并查集 路径压缩 字典树)(困难)的相关文章

poj 2513 Colored Sticks 欧拉回路(字典树 +并查集)

此题中涉及三个小算法,这是一个无向图判断欧拉回路, 无向图存在欧拉回路的充要条件 一个无向图存在欧拉回路,当且仅当该图只存在0或2个奇数度数的顶点,且该图是连通图. 有向图存在欧拉回路的充要条件 一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图. 判断度数很简单,当时没想明白怎么判断图示连通的,其实只要判断他们的父节点的个数,只要只有一个父节点,那么此图是连通的. 字典树分配一下他们的id就好了,还有卡住的一点就是零图是欧拉图. 还有我做了一个小小的剪芝,但是没有什么效果,只减少了3

POJ 1988 Cube Stacking(并查集+路径压缩)

题目链接:id=1988">POJ 1988 Cube Stacking 并查集的题目 [题目大意] 有n个元素,開始每一个元素自己 一栈.有两种操作,将含有元素x的栈放在含有y的栈的顶端,合并为一个栈. 另外一种操作是询问含有x元素以下有多少个元素. 用sum数组储存每一个栈中的元素个数.每次合并的时候将sum加到 父亲节点.也就是每一个栈的最底部. 用under数组储存当前节点以下有多少元素.每次合并的时候,就能够将顶端元素的under赋值为父节点也就是栈最底部的sum. void U

poj 2513 Colored Sticks 并查集 字典树 欧拉回路判断

点击打开链接题目链接 Colored Sticks Time Limit: 5000MS   Memory Limit: 128000K Total Submissions: 30273   Accepted: 8002 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 sti

POJ 2513 Colored Sticks(欧拉回路,字典树,并查集)

题意:给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的. 转:kuangbing 无向图存在欧拉路的充要条件为: ①     图是连通的: ②     所有节点的度为偶数,或者有且只有两个度为奇数的节点. 图的连通可以利用并查集去判断. 度数的统计比较容易. view code//第一次用指针写trie,本来是用二维数组,发现数组开不下,只好删删改改,改成指针 //做这道题,知道了欧拉回路判定,还有用指针写trie #include

POJ 2513 Colored Sticks(字典树+并查集连通性+欧拉回路)

题目地址:POJ 2513 刚开始没想到字典树,用的map函数一直TLE,由于上一次的签到题由于没想到字典树而卡了好长时间的深刻教训,于是过了不久就想起来用字典树了,(为什么是在TLE了5次之后..T^T)然后把map改成了字典树,然后就过了. 这题居然不知不觉的用上了欧拉回路..其实当时我是这样想的..因为相互接触的必须要相同,所以除了两端外,其他的都是两两相同的,所以除了两端的颜色外其他的的个数必须为偶数.然后两端的可能相同可能不相同,相同的话,说明所有的都是偶数个数了,不相同的话那就只有这

poj 2513 Colored Sticks(欧拉通路+并查集+字典树)

题目链接:poj 2513 Colored Sticks 题目大意:有N个木棍,每根木棍两端被涂上颜色,现在给定每个木棍两端的颜色,不同木棍之间拼接需要颜色相同的 端才可以,问最后能否将N个木棍拼接在一起. 解题思路:欧拉通路+并查集+字典树.欧拉通路,每个节点的统计度,度为奇数的点不能超过2个.并查集,判断节点 是否完全联通.字典树,映射颜色. #include <cstdio> #include <cstring> #include <string> #includ

[ACM] POJ 2513 Colored Sticks (Trie树,欧拉通路,并查集)

Colored Sticks Time Limit: 5000MS   Memory Limit: 128000K Total Submissions: 29736   Accepted: 7843 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 st

测试赛A - Colored Sticks(并查集+字典树+欧拉回路)

A - Colored Sticks Time Limit:5000MS     Memory Limit:128000KB     64bit IO Format:%I64d & %I64u Submit Status 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 sti

poj 2513 Colored Sticks(欧拉路径+并检查集合+特里)

题目链接:poj 2513 Colored Sticks 题目大意:有N个木棍,每根木棍两端被涂上颜色.如今给定每一个木棍两端的颜色.不同木棍之间拼接须要颜色同样的 端才干够.问最后是否能将N个木棍拼接在一起. 解题思路:欧拉通路+并查集+字典树. 欧拉通路,每一个节点的统计度,度为奇数的点不能超过2个.并查集,推断节点 是否全然联通. 字典树,映射颜色. #include <cstdio> #include <cstring> #include <string> #i