POJ_2337_オイラーリターン+欲張り
5092 ワード
タイトルリンク:http://poj.org/problem?id=2337
オーラループ関連の定理:
1無方向図はオーラ図であり、連通図であり、すべての頂点の度が偶数である場合のみである.
2無方向図は半オーラ図であり、連通図であり、2つの頂点の度が奇数である場合を除き、他のすべての頂点の度は偶数である.
3方向図はオーラ図であり、ベース図のみが連通しており、すべての頂点の入度は出度に等しい.(図のすべてのエッジに向かう方向を無視し、得られた無方向図をその有方向図のベース図と呼ぶ.)
4方向図は半オーラ図であり、ベース図のみが連通しており、頂点の入度比出度が1より大きく、入度比出度が1より小さく、他のすべての頂点の入度が出度に等しい.
以上の定理は,図がオーラ図であるか否かを判断するために用いられる.
オーラループ(パス)のアルゴリズムを求めます.
時間複雑度O(E)
最後にスタックの各エッジを順次取り出して図のオーラ戻り路を得る.(上記ダミーコードは無方向図であり、有向図であれば//1の行を外せばよい)
(注意、オイラー道路を求める場合、無方向図であれば度数が奇数の点から、有方向図であれば入度より1大きい点から)
この問題に関連して,ディクショナリシーケンスの最小のオーラループ(道路)が要求される場合,単語を用いて有向図を作成し,隣接表の形式で図を格納し,頂点ごとに,それから出たエッジをディクショナリ昇順に並べ,回路が存在する場合,a−zの最小の頂点から,上記アルゴリズムに従ってオーラループを求め,道路が存在する場合,固定点から出発して辞書順の最小の回路(道路)を求めることができる.
コードは次のとおりです.
オーラループ関連の定理:
1無方向図はオーラ図であり、連通図であり、すべての頂点の度が偶数である場合のみである.
2無方向図は半オーラ図であり、連通図であり、2つの頂点の度が奇数である場合を除き、他のすべての頂点の度は偶数である.
3方向図はオーラ図であり、ベース図のみが連通しており、すべての頂点の入度は出度に等しい.(図のすべてのエッジに向かう方向を無視し、得られた無方向図をその有方向図のベース図と呼ぶ.)
4方向図は半オーラ図であり、ベース図のみが連通しており、頂点の入度比出度が1より大きく、入度比出度が1より小さく、他のすべての頂点の入度が出度に等しい.
以上の定理は,図がオーラ図であるか否かを判断するために用いられる.
オーラループ(パス)のアルゴリズムを求めます.
時間複雑度O(E)
Procedure Euler-circuit (start);
Begin
For start v Do
If (start,v) Then Begin
(start,v) ;
(v,start) ; //1
Euler-circuit (v);
;
End;
End;
最後にスタックの各エッジを順次取り出して図のオーラ戻り路を得る.(上記ダミーコードは無方向図であり、有向図であれば//1の行を外せばよい)
(注意、オイラー道路を求める場合、無方向図であれば度数が奇数の点から、有方向図であれば入度より1大きい点から)
この問題に関連して,ディクショナリシーケンスの最小のオーラループ(道路)が要求される場合,単語を用いて有向図を作成し,隣接表の形式で図を格納し,頂点ごとに,それから出たエッジをディクショナリ昇順に並べ,回路が存在する場合,a−zの最小の頂点から,上記アルゴリズムに従ってオーラループを求め,道路が存在する場合,固定点から出発して辞書順の最小の回路(道路)を求めることができる.
コードは次のとおりです.
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct node//graph's node
{
int v,vis;
char str[21];
node()
{
vis = 0;
v = -1;
}
bool operator < (const node &n) const
{
return strcmp(str,n.str)<0;
}
};
const int MAXN = 26;
vector<node> g[MAXN];
stack<char*> S;
int used[MAXN],p[MAXN],in[MAXN],out[MAXN];
void addEdge(char *str)
{
int l = strlen(str)-1;
int u = str[0]-'a',v = str[l]-'a';
node edge;
edge.v = v;
strcpy(edge.str,str);
g[u].push_back(edge);
}
void edgesort()
{
for(int i=0;i<26;i++)if(used[i])
{
sort(g[i].begin(),g[i].end());
}
}
void init()
{
memset(used,0,sizeof(used));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int i=0;i<MAXN;i++)p[i]=i,g[i].clear();
while(!S.empty())S.pop();
}
int find(int x)
{
return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1==r2)return;
p[r1] = r2;
}
bool conn()
{
int cnt = 0 ;
for(int i=0;i<26;i++)
{
if(used[i]&&p[i]==i)cnt++;
}
return cnt==1;
}
bool euler_formula(int &id)
{
int cnt_big=0,cnt_less=0;id = -1;
for(int i=0;i<26;i++)
{
if(used[i])
{
if(in[i]==out[i])continue;
if(in[i]-out[i]==1)cnt_big++;
else if(in[i]-out[i]==-1)cnt_less++,id=i;
else return 0;
}
}
if(!cnt_big&&!cnt_less)return 1;
if(cnt_big==1&&cnt_less==1)return 1;
return 0;
}
void euler_path(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i].v;
if(!g[u][i].vis)
{
g[u][i].vis = 1;
euler_path(v);
S.push(g[u][i].str);
}
}
}
void print_path()
{
char *str = S.top();
S.pop();
printf("%s",str);
while(!S.empty())
{
str = S.top();S.pop();
printf(".%s",str);
}
printf("
");
}
int main()
{
int t,n;char str[21];
scanf("%d%*c",&t);
while(t--)
{
scanf("%d%*c",&n);
init();
for(int i=0;i<n;i++)
{
scanf("%s%*c",str);
addEdge(str);
int l = strlen(str)-1;
int u = str[0]-'a',v = str[l]-'a';
used[u]=used[v]=1;
out[u]++,in[v]++;
merge(u,v);
}
int id;
bool ok = euler_formula(id)&&conn();
edgesort();
if(ok)
{
if(id==-1)
{
for(int i=0;i<26;i++)
{
if(used[i])
{
euler_path(i);
break;
}
}
}
else euler_path(id);
print_path();
}
else
{
printf("***
");
}
}
return 0;
}