POJ-2153Colored Sticks解题报告+欧拉回路，字典树，并查集；

传送门：http://poj.org/problem?id=2513

题意：给你许多木棍，木棍两端都有颜色，问能不能首尾相接，要求颜色相同。

参考：https://www.cnblogs.com/kuangbin/archive/2012/08/07/2626223.html

思路：

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

① 图是连通的；

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

图的连通可以利用并查集去判断。

度数的统计比较容易。

数据比较大，首先需要将颜色的字符串和数字一一对应起来。

虽然可以用map,但是map效率不高，肯定会超时的。

最好的办法的是建立字典树。

将字符串和数字一一对应起来。

注意本题的数据有没有木棒的情况，要输出Possible。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <list>

#include <iterator>

using namespace std;

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define Pll pair<ll,ll>

#define Pii pair<int,int>

#define fi first

#define se second

#define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

typedef long long ll;

typedef unsigned long long ull;

/*-----------------show time----------------*/

const int tm = ;

int col = ;

struct trie{

    trie* nxt[tm];

    int last;

    trie()

    {

        memset(nxt,,sizeof(nxt));

        last = ;

    }

}*root;

int insert(char *s)

{

    trie * p = root;

    for(int i=;s[i];i++)

    {

        if(!p->nxt[s[i] - 'a'])

            p->nxt[s[i]-'a'] = new trie;

        p = p->nxt[s[i]-'a'];

    }

    if(p->last)

        return p->last;

    else

    {

        col++;

        return p->last = col;

    }

}

const int maxn = 5e5+;

int deg[maxn];

int fa[maxn];

void init(){

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

        fa[i] = i;

    root = new trie;

}

int f(int x)

{

    if(fa[x]==x)return x;

    else return fa[x] = f(fa[x]);

}

void uni(int x,int y)

{

    int px = f(x);

    int py = f(y);

    if(px==py)return ;

    fa[px] = py;

}

int main(){

    char s1[],s2[];

    init();

    while(~scanf("%s%s",s1,s2))

    {

        // if(s1[0]==s2[0])break;

        int x = insert(s1),y = insert(s2);

        uni(x,y);

        deg[x]++;

        deg[y]++;

    }

    int cnt1 = ,cnt2 = ;

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

    {

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

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

    }

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

    {

        puts("Possible");

    }

    else puts("Impossible");

    return ;

}

巴特西

POJ-2153Colored Sticks解题报告+欧拉回路，字典树，并查集；

最新文章

热门文章