POJ2513Colored Sticks（欧拉通路）（字典树)(并查集）

时间：2021-10-18 05:18:13
                                                         Colored Sticks
Time Limit: 5000MS   Memory Limit: 128000K
Total Submissions: 35612   Accepted: 9324

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
【分析】欧拉通路的判定。一开始用map给字符串编号，超时了，后来在网上烤来一份字典树hash.

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#include<functional>

#define mod 1000000007

#define inf 0x3f3f3f3f

#define pi acos(-1.0)

using namespace std;

typedef long long ll;

const int N=;

const int M=;

ll power(ll a,int b,ll c){ll ans=;while(b){if(b%==){ans=(ans*a)%c;b--;}b/=;a=a*a%c;}return ans;}

int parent[N];

const int MAX=;

int degree[N];//度数

int color;//颜色编号，从0开始，最后就是颜色总数

int Find(int x) {

    if(parent[x] != x) parent[x] = Find(parent[x]);

    return parent[x];

}//查找并返回节点x所属集合的根节点

void Union(int x,int y) {

    x = Find(x);

    y = Find(y);

    if(x == y) return;

    parent[y] = x;

}//将两个不同集合的元素进行合并

struct Trie

{

    bool isWord;

    struct Trie *next[MAX];

    int id;

};

int insert(Trie *root,char *word)//返回颜色编号

{

    Trie *p=root;

    int i=;

    while(word[i]!='\0')

    {

        if(p->next[word[i]-'a']==NULL)

        {

            Trie *temp=new Trie;

            temp->isWord=false;

            for(int j=;j<MAX;j++)

              temp->next[j]=NULL;

            temp->isWord=false;

            temp->id=;

            p->next[word[i]-'a']=temp;

        }

        p=p->next[word[i]-'a'];

        i++;

    }

    if(p->isWord)

    {

        return p->id;

    }

    else

    {

        p->isWord=true;

        p->id=color++;

        return p->id;

    }

}

void del(Trie *root)

{

    for(int i=;i<MAX;i++)

    {

        if(root->next[i]!=NULL)

         del(root->next[i]);

    }

    free(root);

}

int main()

{

    char str1[],str2[];

    Trie *root=new Trie;

    for(int i=;i<MAX;i++)

      root->next[i]=NULL;

    root->isWord=false;

    root->id=;//初始化

    color=;

    for(int i=;i<N;i++)parent[i]=i;

    memset(degree,,sizeof(degree));

    while(scanf("%s%s",&str1,&str2)!=EOF)

    {

        int t1=insert(root,str1);

        int t2=insert(root,str2);

     //   printf("%d %d\n",t1,t2);

        degree[t1]++;

        degree[t2]++;

        Union(t1,t2);

    }

    int cnt1=,cnt2=;

    for(int i=;i<color;i++)

    {

        if(parent[i]==i)cnt1++;

        if(degree[i]%==)cnt2++;

        if(cnt1>)break;

        if(cnt2>)break;

    }

    //数据比较坑人，存在0根木棒的情况，此时cnt1==0

    if((cnt1==||cnt1==)&&(cnt2==||cnt2==))

      printf("Possible\n");

    else printf("Impossible\n");

    //del(root);//单组输入可以不释放空间，可以节省时间

    return ;

}

相关文章