洛谷 P1341 无序字母对（欧拉迹）

78 阅读 0 评论 52 点赞

我是靠谱客的博主害羞草丛，最近开发中收集的这篇文章主要介绍洛谷 P1341 无序字母对（欧拉迹），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：

有字母对，问我们允许字母对中字母对调，可以把这串字母首尾相接吗？能够的情况下，问怎么让结果字典序最小。

比如，ab cb，我们可以通过对调第二对字母的cb为bc从而得到，ab bc首尾相接。

解题思路：

我们把字母当作节点，同一个字母对中字母连一条边，然后跑欧拉回路即可。另外这里需要字典序最小，我们在用fluery算法跑欧拉回路时，优先选择排序靠前的节点即可。

废话：

注意，欧拉回路必须满足以下条件：

（1）图中只有一个连通分量

（2）奇数度顶点只有0或者2个

#include <bits/stdc++.h>
using
namespace std;
const int MAXN=26+26;
vector<vector<int>> gra(MAXN);
vector<vector<int>> gra2(MAXN);
int flag[MAXN];
vector<pair<char,char>> ans;
set<int,less<int>> oddstart;
// A class that represents an undirected graph
class Graph
{
int V; // No. of vertices
list<int> *adj; // A dynamic array of adjacency lists
public:
// Constructor and destructor
Graph(int V) { this->V = V; adj = new list<int>[V]; }
~Graph()
{ delete [] adj; }
// functions to add and remove edge
void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }
void rmvEdge(int u, int v);
// Methods to print Eulerian tour
void printEulerTour();
void printEulerUtil(int s);
// This function returns count of vertices reachable from v. It does DFS
int DFSCount(int v, bool visited[]);
// Utility function to check if edge u-v is a valid next edge in
// Eulerian trail or circuit
bool isValidNextEdge(int u, int v);
};
/* The main function that print Eulerian Trail. It first finds an odd
degree vertex (if there is any) and then calls printEulerUtil()
to print the path */
void Graph::printEulerTour()
{
// Find a vertex with odd degree
int u;
auto it=oddstart.begin();
if(oddstart.size())u=*next(it,0);
else{
for(int i=0;i<MAXN;i++)
if(gra[i].size()){
u=i;
break;
}
}
printEulerUtil(u);
}
// Print Euler tour starting from vertex u
void Graph::printEulerUtil(int u)
{
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i;
// If edge u-v is not removed and it's a a valid next edge
if (v != -1 && isValidNextEdge(u, v))
{
int res[2];
res[0]=u;res[1]=v;
char c[2];
for(int ii=0;ii<2;ii++){
if(res[ii]>=0 && res[ii]<=25)c[ii]=res[ii]+'A';
else c[ii]=res[ii]-26+'a';
}
ans.push_back(make_pair(c[0],c[1]));
rmvEdge(u, v);
printEulerUtil(v);
}
}
}
// The function to check if edge u-v can be considered as next edge in
// Euler Tout
bool Graph::isValidNextEdge(int u, int v)
{
// The edge u-v is valid in one of the following two cases:
// 1) If v is the only adjacent vertex of u
int count = 0; // To store count of adjacent vertices
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (*i != -1)
count++;
if (count == 1)
return true;
// 2) If there are multiple adjacents, then u-v is not a bridge
// Do following steps to check if u-v is a bridge
// 2.a) count of vertices reachable from u
bool visited[V];
memset(visited, false, V);
int count1 = DFSCount(u, visited);
// 2.b) Remove edge (u, v) and after removing the edge, count
// vertices reachable from u
rmvEdge(u, v);
memset(visited, false, V);
int count2 = DFSCount(u, visited);
// 2.c) Add the edge back to the graph
addEdge(u, v);
// 2.d) If count1 is greater, then edge (u, v) is a bridge
return (count1 > count2)? false: true;
}
// This function removes edge u-v from graph. It removes the edge by
// replacing adjcent vertex value with -1.
void Graph::rmvEdge(int u, int v)
{
// Find v in adjacency list of u and replace it with -1
list<int>::iterator iv = find(adj[u].begin(), adj[u].end(), v);
*iv = -1;
// Find u in adjacency list of v and replace it with -1
list<int>::iterator iu = find(adj[v].begin(), adj[v].end(), u);
*iu = -1;
}
// A DFS based function to count reachable vertices from v
int Graph::DFSCount(int v, bool visited[])
{
// Mark the current node as visited
visited[v] = true;
int count = 1;
// Recur for all vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if (*i != -1 && !visited[*i])
count += DFSCount(*i, visited);
return count;
}
void dfs(int u){
flag[u]=1;
for(int i=0;i<(int)gra2[u].size();i++){
int nx=gra2[u][i];
if(!flag[nx])dfs(nx);
}
}
int main(){
int n;cin>>n;
for(int i=0;i<n;i++){
string t;cin>>t;
sort(t.begin(),t.end());
int poi[2];
//cerr<<t[0]<<" "<<t[1]<<endl;
for(int ii=0;ii<2;ii++){
if(t[ii]>='A' && t[ii]<='Z')poi[ii]=t[ii]-'A';
else poi[ii]=t[ii]-'a'+26;
}
gra[poi[0]].emplace_back(poi[1]);
gra2[poi[0]].emplace_back(poi[1]);
gra2[poi[1]].emplace_back(poi[0]);
}
for(int i=0;i<MAXN;i++)sort(gra[i].begin(),gra[i].end(),less<int>());
memset(flag,0,sizeof(flag));
int count=0;
for(int i=0;i<MAXN;i++){
for(int j=0;j<(int)gra2[i].size();j++){
if(!flag[gra2[i][j]])
{
if(count>0){
//cerr<<"circle"<<endl;
cout<<"No Solution"<<endl;
return 0;
}
dfs(gra2[i][j]);
count++;
}
}
}
for(int i=0;i<MAXN;i++){
int deg=gra2[i].size();
//cerr<<deg<<endl;
if(deg%2==1)oddstart.insert(i);
}
if(!(oddstart.size()==0 || oddstart.size()==2)){
cout<<"No Solution"<<endl;
return 0;
}
Graph g(MAXN);
for(int i=0;i<(int)MAXN;i++)
for(int j=0;j<(int)gra[i].size();j++){
int nx=gra[i][j];
//cerr<<i<<" "<<nx<<endl;
g.addEdge(i, nx);
}
g.printEulerTour();
for(int i=0;i<(int)ans.size();i++){
if(i==(int)ans.size()-1)cout<<ans[i].first<<ans[i].second<<endl;
else cout<<ans[i].first;
}
return 0;
}