首页 > 代码库 > poj 2337 Catenyms 【欧拉路径】
poj 2337 Catenyms 【欧拉路径】
题目链接:http://poj.org/problem?id=2337
题意:给定一些单词,假设一个单词的尾字母与还有一个的首字母同样则能够连接。问能否够每一个单词用一次,将全部单词连接,能够则输出字典序最小的序列。
代码:
(bin 神的板子)
#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
using namespace std;
int t;
int n;
string s[1010];
struct Edge
{
int to, next;
int index;
bool flag;
}edge[2010];
int head[300], tot;
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u, int v, int index)
{
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].index = index;
edge[tot].flag = false;
head[u] = tot++;
}
int in[250], out[250];
int cnt;
int ans[1010];
void dfs(int u)
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
if (!edge[i].flag)
{
edge[i].flag = true;
dfs(edge[i].to);
ans[cnt++] = edge[i].index;
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
scanf("%d",&n);
for (int i = 0; i < n; i++)
cin >> s[i];
sort(s, s + n);
init();
memset(in,0,sizeof(in));
memset(out, 0, sizeof(out));
int start = 100;
for (int i = n - 1; i >= 0; i--)
{
int u = s[i][0] - ‘a‘;
int v = s[i][s[i].length() - 1] - ‘a‘;
addedge(u,v,i);
out[u]++;
in[v]++;
if (u < start) start = u;
if (v < start) start = v;
}
int cc1 = 0, cc2 = 0;
for (int i = 0; i < 26; i++)
{
if (out[i] - in[i] == 1)
{
cc1++;
start = i;
}
else if (out[i] - in[i] == -1)
cc2++;
else if (out[i] - in[i] != 0)
cc1 = 3;
}
if (!((cc1 == 0 && cc2 == 0) || (cc1 == 1 && cc2 == 1)))
{
printf("***\n");
continue;
}
cnt = 0;
dfs(start);
if (cnt != n)
{
printf("***\n");
continue;
}
for (int i = n-1; i >=0 ; i--)
{
cout << s[ans[i]];
if (i != 0) printf(".");
else printf("\n");
}
}
return 0;
}
poj 2337 Catenyms 【欧拉路径】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。