POJ 2513 Colored Sticks (排序+并查集判斷歐拉路)

題意:

給一堆棍子,棍子由頭尾兩個字元串組成,棍子兩兩相連的條件是相接的部分字元串必須相同,問能否将這些棍子組成一條直線.

解題過程:

這題其實并不需要用字典樹處理,用排序統計度數一樣.

一開始我想到保證度數為奇數的點的數量小于2就行了,但這樣明顯不可以,點數為1時就不正确.

另外最重要的一點,當度數為奇數的點數量為0或2時,可以保證每條邊都會被周遊且隻有一次,但是,這樣的圖有可能是多個歐拉分路組成的非連通圖.是以仍然不能滿足題目要求.

然後我改用并查集判斷是否連通,送出仍然WA,去網上看了下别人的做法,除了用字典樹統計度數其它沒有差别,直到我看到kuangbin大神的部落格裡寫着要考慮沒有棍子的情況.....暈.

正确思路:

題目等價與判斷圖是否是歐拉圖

判斷歐拉圖條件

1.圖連通

2.度數為奇數的點的個數為0或奇數.

條件一用并查集判斷是否滿足即可

條件二用字典樹或排序都可以統計判斷是否滿足.

注意棍子為0的資料,答案應該是可以.

代碼:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int f[501234];
struct p
{
    char a[15];
    int v;  // 對點編号.
}b[501234];
int cmp(p a, p b )
{
    return strcmp(a.a,b.a)<0;
}
int getf(int x)
{
    if(x==f[x])return x;
    else return f[x]=getf(f[x]);
}
void merg(int x, int y)
{
    x=getf(x);
    y=getf(y);
    if(x!=y)
    {
        f[y]=x;
    }
}
int main()
{
    int i=0;
    i=0;
    while(~scanf("%s", b[i].a))
    {
        b[i].v=i/2;
        i++;
        b[i].v=i/2;
        scanf("%s", b[i++].a);
    }
    sort(b, b+i, cmp);
    int n;
    n=i;
    for(i=0; i<n/2; i++)f[i]=i;
    int sum=1;   //相同字元串個數,即點的度數.
    int tosum=0; //度數為奇數點的個數
    <pre name="code" class="cpp">    for(i=0; i<n-1; i++)
    {

        if(strcmp(b[i].a, b[i+1].a)==0)
        {
            sum++;
            merg(b[i].v, b[i+1].v);
        }
        else
        {
            if(sum%2)tosum++;
            sum=1;
        }
    }
    if(sum%2)tosum++; //最後判斷下最後一個點的度數是否是奇數.
    
    for(i=0; i<n/2-1; i++)
    {
       if(getf(i)!=getf(i+1))break;
    }
    
    if((tosum==0 || tosum==2) && i==n/2-1) printf("Possible\n");
    else if(n==0)printf("Possible\n");  //棍子為0的情況
    else printf("Impossible\n");
    return 0;
}