POJ 2337 有向图的欧拉路径

Description

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog

Input

Output

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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
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.name<b.name;
}
bool app[30],use[maxn];
int in[30],out[30],fa[40],s[maxn];
int find(int x){
	if(fa[x]==0)return x;
	fa[x]=find(fa[x]);
		return fa[x];
}
bool euler(){
	int t=0;
	for(int i=1;i<=26;i++)
		if(app[i]){
			if(t==0)t=find(i);
			if(find(i)!=t)return 0;
		}
	int sum=0;
	S=0;
	for(int i=1;i<=26;i++)
		if(app[i]){
			if(in[i]!=out[i]){
				if(abs(in[i]-out[i])>1)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<<road[s[i]].name<<‘.‘;
		 cout<<road[s[1]].name<<endl;
	 }
     return 0;
}

POJ 2337 有向图的欧拉路径,布布扣,bubuko.com

POJ 2337 有向图的欧拉路径

原文：http://blog.csdn.net/xianxingwuguan1/article/details/22090641