POJ 2337 Catenyms(有向欧拉图:输出欧拉路径)

题目链接>>>>>>

题目大意:

给出一些字符串,问能否将这些字符串  按照 词语接龙,首尾相接  的规则 使得每个字符串出现一次

如果可以 按字典序输出这个字符串序列

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#define M 1050
using namespace std;
int n, top;
struct edge {
int to, vis, id; //to代表边的终点,id代表边的编号
};
vector<edge>w[M];
string str[M]; //原来还可以这样定义字符串数组
int ans[M];
int fa[]; int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
} void fleury(int loc)
{
for (int i = ; i<w[loc].size(); i++)
if (!w[loc][i].vis)
{
w[loc][i].vis = ;
fleury(w[loc][i].to);
ans[top++] = w[loc][i].id;
}
return;
} int main()
{
int indegree[], outdegree[];
int T;
scanf("%d", &T);
while (T--)
{
top = ;
for (int i = ; i<; i++)
{
w[i].clear();
outdegree[i] = indegree[i] = ;
fa[i] = i;
}
scanf("%d", &n);
int a, b;
for (int i = ; i<n; i++)
cin >> str[i];
sort(str, str + n); //根据字典序排序
edge edg;
int start;
for (int i = ; i<n; i++)
{
a = str[i][] - 'a';
b = str[i][str[i].size() - ] - 'a';
indegree[a]++;
outdegree[b]++;
fa[find(a)] = find(b);
edg.to = b; edg.vis = ; edg.id = i;
w[a].push_back(edg);
if (i == ) //重要 起点必须为初始化为第一条边的出节点(字典序最小,且满足 欧拉回路 的的要求)
start = a;
} int ss = , num = , start_num = , end_num = ;
for (int i = ; i<; i++)
{
if ((indegree[i] || outdegree[i]) && find(i) == i) //find(i)==i是用来判断整个图是否连通的,因为图存在欧拉通路的条件之一就是必须是连通图
ss++; //结合下面的ss==1,来理解,因为如果整个图是连通的,ss就只会在当i为根节点的时候+1
if (indegree[i] != outdegree[i])
{
if (outdegree[i] - indegree[i] == -)
start = i, start_num++; //这里和上面的初始化start的步骤不懂,做题的时候就是卡在了选取第一个出节点的步骤
else if (outdegree[i] - indegree[i] == )
end_num++;
num++;
}
}
if ((num == || (num == && start_num == && end_num == )) && ss == ) //存在欧拉通路的条件
{
fleury(start); //我对start的选取不是很理解
for (int i = top - ; i >= ; i--) //要使输出的单词按字典序输出
{
if (i == )
cout << str[ans[i]] << endl;
else
cout << str[ans[i]] << ".";
}
}
else
cout << "***" << endl;
}
return ;
}

2018-04-07

上一篇:[译]Quartz.NET 框架 教程(中文版)2.2.x 之第四课 更多关于Triggers


下一篇:【MySQL】MySQL查询数据库各表的行数