poj2337

這道題昨天晚上開(kāi)始做，今天才A。但是問(wèn)題想透了， 發(fā)現(xiàn)其實(shí)沒(méi)那么難

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

?

#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//結(jié)構(gòu)體：邊， 存儲(chǔ)了邊的起點(diǎn)（首字符）和終點(diǎn)（尾字符），狀態(tài)（是否走過(guò)） {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)//查找其父節(jié)點(diǎn) {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]++;/*如果存在歐拉路徑，那么所有的點(diǎn)一定都連通.所有的點(diǎn)都在一個(gè)集合里，可以用并查集知識(shí)將所有連接的點(diǎn)并到一起。*/int fx = find(s);int fy = find(e);if(fx != fy)pre[fx] = fy;}sort(edge + 1, edge + 1 + n, cmp);//題目要求字典序最小輸出，就先按從小到大的順序把邊（單詞）排好/*st代表的是路徑起點(diǎn)，在這里進(jìn)行st = edge[1].s賦值，是應(yīng)為存在兩種情況：1.存在一定點(diǎn)出度>入度,這個(gè)點(diǎn)是起點(diǎn)。2.所有點(diǎn)出度= 入度， 那么從任意一點(diǎn)出發(fā)都可以， 為了保證字典序最小， 就從第一個(gè)單詞開(kāi)始*/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;}//起點(diǎn)else if(in[i] == out[i] + 1) c2++;else break;}//如果符合了連通圖，并且存在歐拉通路， 就開(kāi)始找路徑if(i == 27 && ((c1 == c2 && c1 == 1) || (c1 == c2 && c1 == 0)) && panduan() == 1){k = 0;path(st);for(int i = n; i > 1; i--)//輸出這注意點(diǎn)，因?yàn)槭沁f歸求的路徑， 最先得到的是最后的邊printf("%s.", edge[step[i]].c);printf("%s\n", edge[step[1]].c);}elseprintf("***\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wd-one/p/4539305.html

總結(jié)

以上是生活随笔為你收集整理的poj2337 欧拉路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。