poj2337 歐拉路徑，poj2337歐拉路徑

poj2337 歐拉路徑，poj2337歐拉路徑

poj2337

這道題昨天晚上開始做，今天才A。但是問題想透了， 發現其實沒那麼難

題目大意： 
給你一些單詞，如果一個單詞的末尾字符與另一個單詞首字符相同，則兩個的單詞可以連接。問是否可以把所有單詞連接起來，並且每個單詞只能用一次。 
分析： 
可以把每個單詞看成是一條邊，單詞的首尾字符看做是兩個相連的點。我們可以把它看成有向圖的歐拉路徑問題（歐拉路徑，歐拉回路不太明白的自己百度吧）。 
一個有向圖含有歐拉通路，首先圖是連通的，並且當且僅當該圖所有頂點的入度 =出度， 或者起始頂點入度 = 出度 - 1 ，結束點 出度＝入度－１，　其余點入度＝　出度。明白了這些，我們的思路也就清晰啦！ 
重點來啦：首先判斷圖是否連通的，在判斷圖是否存在歐拉路徑，如果都符合那就找路徑。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;

int out[30], in[30], step[1005], pre[30];
int n, k, t, st;
char w[25];

struct Edge//結構體：邊， 存儲了邊的起點（首字符）和終點（尾字符），狀態（是否走過）
{
    int s, e, v;
    char c[25];
}edge[1005];

bool cmp(Edge x, Edge y)
{
    return strcmp(x.c, y.c) < 0 ? true : false;
}
int find(int x)//查找其父節點
{
    if(pre[x] != x)
        pre[x] = find(pre[x]);
    return pre[x];
}
int panduan()//判斷是否圖是連通的
{
    int fx = find(edge[1].s);
    for(int i = 1; i <= 26; i++)
    {
        if(out[i] > 0 || in[i] > 0)
        {
            if(find(i) != fx)
                return 0;
        }
    }
    return 1;
}
void path(int en)//查找路徑
{
    for(int i = 1; i <= n; i++)
    {
        if(edge[i].v == 0 && edge[i].s == en)
        {
            edge[i].v = 1;
            path(edge[i].e);
            step[++k] = i;
        }
    }
}
int main()
{
    cin >> t;
    while(t--)
    {
        memset(out, 0, sizeof(out));
        memset(in, 0, sizeof(in));
        memset(step, 0, sizeof(step));
        for(int i = 1; i <= 30; i++)
            pre[i] = i;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            cin >> w;
            int len = strlen(w);
            int s = w[0] - 'a' + 1;
            int e = w[len - 1] - 'a' + 1;
            edge[i].s = s;
            edge[i].e = e;
            strcpy(edge[i].c, w);
            edge[i].v = 0;

            out[s]++;
            in[e]++;
            /*如果存在歐拉路徑，那麼所有的點一定都連通.所有的點都在一個集合裡，可以用並查集知識
            將所有連接的點並到一起。*/
            int fx = find(s);
            int fy = find(e);
            if(fx != fy)
                pre[fx] = fy;
        }
        sort(edge + 1, edge + 1 + n, cmp);//題目要求字典序最小輸出，就先按從小到大的順序把邊（單詞）排好
        /*st代表的是路徑起點，在這裡進行st = edge[1].s賦值，是應為存在兩種情況：1.存在一定點出度>入度,
        這個點是起點。2.所有點出度= 入度， 那麼從任意一點出發都可以， 為了保證字典序最小， 就從第一個單詞開始*/
        st = edge[1].s;
        int i, c1 = 0, c2 = 0;
        for(i = 1; i <= 26; i++)//判斷是否有歐拉回路
        {
            if(out[i] == in[i])continue;
            else if(in[i] == out[i] - 1) {c1++; st = i;}//起點
            else if(in[i] == out[i] + 1) c2++;
            else break;
        }
        //如果符合了連通圖，並且存在歐拉通路， 就開始找路徑
        if(i == 27 && ((c1 == c2 && c1 == 1) || (c1 == c2 && c1 == 0)) && panduan() == 1)
        {
            k = 0;
            path(st);
            for(int i = n; i > 1; i--)//輸出這注意點，因為是遞歸求的路徑， 最先得到的是最後的邊
                printf("%s.", edge[step[i]].c);
            printf("%s\n", edge[step[1]].c);
        }
        else
            printf("***\n");
    }
    return 0;
}