程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2337 有向圖的歐拉路徑

POJ 2337 有向圖的歐拉路徑

編輯：C++入門知識

Catenyms Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8857 Accepted: 2336

Description

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,

aloha.aloha.arachnid.dog.gopher.rat.tiger

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

Input

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

Output

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

Sample Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger
***

單詞接龍，形成歐拉路徑。

計算方法：

（1) 在輸入詞典的同時構造有向圖G，計算每一個節點所在的入度和並查集所在的根，

（2）將邊按照字典序排列。

（3）按照遞增順序搜索每一個節點，若相鄰兩個節點屬於不同的並查集，則說明圖無法按照字典序形成若連通圖，有向歐拉路徑不存在。否則進行4

（4）按照遞增順序搜索每一個節點，若存在入度出度相差大於1的節點，則有向圖歐拉路徑不存在，否則，若所有的節點出入度相同，則選擇序號最下的節點

作為歐拉回路的起點，若存在一個出度比入度大一的頂點，則該節點作為有向歐拉路徑的起點，

（5）從S出發dfs計算有向圖歐拉路徑

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/3/25 19:03:35
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=1100;
struct node{
	int u,v;
	string name;
}road[maxn];
int n,S,stop,t;
bool cmp(node a,node b){
	return a.name1)return 0;
				sum++;
				if(out[i]>in[i])S=i;
			}
		}
	if(sum==0){
		for(int i=1;i<26;i++)
			if(app[i]){
				S=i;
				break;
			}
	}
	return 1;
}
void dfs(int now){
	for(int i=1;i<=n;i++)
		if(!use[i]&&road[i].u==now){
			use[i]=1;
			dfs(road[i].v);
			s[++stop]=i;
		}
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
	 int T;
	 cin>>T;
     while(T--){
		 cin>>n;
		 memset(in,0,sizeof(in));
		 memset(out,0,sizeof(out));
		 memset(fa,0,sizeof(fa));
		 memset(app,0,sizeof(app));
		 for(int i=1;i<=n;i++){
		 cin>>road[i].name;
		    road[i].u=road[i].name[0]-'a'+1;
		    road[i].v=road[i].name[road[i].name.length()-1]-'a'+1;
		    app[road[i].u]=1;
		    app[road[i].v]=1;
		    int u=find(road[i].u);
		    int v=find(road[i].v);
		    if(u!=v)fa[u]=v;
		    out[road[i].u]++;in[road[i].v]++;
		 }
		 sort(road+1,road+n+1,cmp);
		 if(!euler()){
			 puts("***");
			 continue;
		 }
		 stop=0;
		 memset(use,0,sizeof(use));
		 dfs(S);
		 for(int i=stop;i>=2;i--)cout<