poj2513字典树+欧拉图判断+并查集断连通

题意：俩头带有颜色的木棒，要求按颜色同的首尾相连，可能否？

思路：棒子本身是一条边，以俩端为顶点（同颜色共点），即求是否有无向图欧拉路（每条棒子只有一根，

边只能用一次，用一次边即选一次棒子）。

先判断图是否连通，并查集判断即可，有fa[i]==i的，表示“根”，连通图只能有一个这样根，大于1不连通。

在判断欧了图是否存在，度权为偶数或者只有2俩奇数为欧拉图，否则不是。

未1a原因：

1，有一段时间没写并查集了，这次并查集，并的时候也写错！SB啊！

2. 特殊情况，0个点的时候输出可能

#include<iostream>  //594ms

#include<cstring>

#include<string>

#include<cstdio>

using namespace std;

int degree[510001];

int trie[1010001][27];int numtrie=0;

int numv=0;

int fa[510001];

int find(int x)

{

    if(x!=fa[x]) fa[x]=find(fa[x]);

    return fa[x];

}

int insert_getnum(string s)  //字典树，本质hash判重，是否同一个颜色，并返回该结点

{

    int u=0;

    int len=s.size();

    for(int i=0;i<len;i++)

    {

        if(trie[u][s[i]-'a']==0)

            trie[u][s[i]-'a']=++numtrie;

        u=trie[u][s[i]-'a'];

    }

    if(trie[u][26]==0)

      trie[u][26]=++numv;

    return trie[u][26];

}

bool is_together()   //是否连通

{

    int count=0;

    for(int i=1;i<=numv;i++)

    {

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

        if(count>1)break;

    }

    if(count>1)return 0;

    return 1;

}

bool is_euler()  //有欧拉？

{

    int count=0;

     for(int i=1;i<=numv;i++)

    {

        if(degree[i]&1)count++;

    }

    if(count==0||count==2)return 1;

    else return 0;

}

int main()

{

    char s1[12],s2[12];

    for(int i=1;i<500001;i++)

           fa[i]=i;

    while(scanf("%s %s",s1,s2)!=EOF)

    {

        string s=s1;

        string ss=s2;

        int x=insert_getnum(s);

        int y=insert_getnum(ss);

        degree[x]++;

        degree[y]++;

        int xx=find(x);     //因为并查集在这里跪了俩次了！

        int yy=find(y);

        if(xx!=yy)           //这样合并啊！

          fa[yy]=xx;

    }

    if(numv==0||is_euler()&&is_together())printf("Possible\n");

    else printf("Impossible\n");

  return 0;

}

巴特西

poj2513字典树+欧拉图判断+并查集断连通

最新文章

热门文章