我想解决这个问题。
我可以通过查看给定结构是否可以形成euler电路的程度来找到，但是我无法找出如何找到给定测试用例的所有路径
5个
2 1个
2 2个
3 4个
3 1个
2 4个
在节点2的电路中有一个循环，我不知道如何跟踪，如果我使用邻接列表表示，那么我将得到以下列表
1:2,3分
2:1、2、2、4
3:1,4分
4:2,3分
所以如何遍历每一条边，我知道这是欧拉回路的问题，但自循环的事情让我很难编码，我没有得到任何教程或博客，从那里我可以理解这件事。
我又想在遍历路径后从邻接列表中删除节点（为了保持euler的属性（路径应该遍历一次）），但我使用vector来存储邻接列表，我不知道如何从vector中删除特定元素。我搜索了一下，找到了从向量中删除的remove命令，但是remove从向量中删除了所有匹配的元素。
我试着解决下面的问题，但是得到了wa:。（
#include<iostream>
#include<cstdio>
#include<cstring>
int G[52][52];
int visited[52],n;
void printadj() {
int i,j;
for(i=0;i<51;i++) {
for(j=0;j<51;j++)
printf("%d ",G[i][j]);
printf("\n");
}
}
void dfs(int u){
int v;
for(v=0;v<51;v++){
if(G[u][v]){
G[u][v]--;
G[v][u]--;
printf("%d %d\n",u,v);
dfs(v);
}
}
}
bool is_euler(){
int i,j,colsum=0,count=0;
for(i=0;i<51;i++) {
colsum=0;
for(j=0;j<51;j++) {
if(G[i][j] > 0) {
colsum+=G[i][j];
}
}
if(colsum%2!=0) count++;
}
// printf("\ncount=%d\n",count);
if(count >0 ) return false;
else return true;
}
void reset(){
int i,j;
for(i=0;i<51;i++)
for(j=0;j<51;j++)
G[i][j]=0;
}
int main(){
int u,v,i,t,k;
scanf("%d",&t);
for(k=0;k<t;k++) {
scanf("%d",&n);
reset();
for(i=0;i<n;i++){
scanf("%d%d",&u,&v);
G[u][v]++;
G[v][u]++;
}
// printadj();
printf("Case #%d\n",k+1);
if(is_euler()) {
dfs(u);
}
else printf("some beads may be lost\n");
printf("\n");
}
return 0;
}
不知道为什么要让wa：（
新代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define max 51
int G[max][max],print_u[max],print_v[max],nodes_traversed[max],nodes_found[max];
int n,m;
void printadj() {
int i,j;
for(i=0;i<max;i++) {
for(j=0;j<max;j++)
printf("%d ",G[i][j]);
printf("\n");
}
}
void dfs(int u){
int v;
for(v=0;v<50;v++){
if(G[u][v]){
G[u][v]--;
G[v][u]--;
print_u[m]=u;
print_v[m]=v;
m++;
dfs(v);
}
}
nodes_traversed[u]=1;
}
bool is_evendeg(){
int i,j,colsum=0,count=0;
for(i=0;i<50;i++) {
colsum=0;
for(j=0;j<50;j++) {
if(G[i][j] > 0) {
colsum+=G[i][j];
}
}
if(colsum&1) return false;
}
return true;
}
int count_vertices(int nodes[]){
int i,count=0;
for(i=0;i<51;i++) if(nodes[i]==1) count++;
return count;
}
void reset(){
int i,j;
m=0;
for(i=0;i<max;i++)
for(j=0;j<max;j++)
G[i][j]=0;
memset(print_u,0,sizeof(print_u));
memset(print_v,0,sizeof(print_v));
memset(nodes_traversed,0,sizeof(nodes_traversed));
memset(nodes_found,0,sizeof(nodes_found));
}
bool is_connected(int tot_nodes,int trav_nodes) {
if(tot_nodes == trav_nodes) return true;
else return false;
}
int main(){
int u,v,i,t,k,tot_nodes,trav_nodes;
scanf("%d",&t);
for(k=0;k<t;k++) {
scanf("%d",&n);
reset();
for(i=0;i<n;i++){
scanf("%d%d",&u,&v);
G[u][v]++;
G[v][u]++;
nodes_found[u]=nodes_found[v]=1;
}
// printadj();
printf("Case #%d\n",k+1);
tot_nodes=count_vertices(nodes_found);
if(is_evendeg()) {
dfs(u);
trav_nodes=count_vertices(nodes_traversed);
if(is_connected(tot_nodes,trav_nodes)) {
for(i=0;i<m;i++)
printf("%d %d\n",print_u[i],print_v[i]);
}
else printf("some beads may be lost\n");
}
else printf("some beads may be lost\n");
printf("\n");
}
return 0;
}
这段代码给了我运行时的错误，请查看代码。
最佳答案
你需要做的是形成任意的循环，然后把所有的循环连接在一起。你似乎只做了一个深度优先遍历，这可能给你一个欧拉回路，但它也可能给你一个欧拉回路的“捷径”。这是因为，在欧拉回路经过多次的每个顶点（即欧拉回路与自身交叉的地方），当深度优先遍历第一次到达该顶点时，欧拉回路可以拾取直接返回深度优先遍历起点的边。
因此，你的算法应该由两部分组成：
查找所有周期
把循环连接在一起
如果做得正确，你甚至不必检查所有顶点都有一个均匀的程度，相反，你可以相信，如果第1步或第2步不能继续下去，就没有欧拉循环。
参考实现（Java）
既然你的问题中没有语言标签，我假设我会给你一个Java参考实现，这对你来说很好。此外，我将使用术语“node”而不是“vertex”，但这只是个人偏好（它提供了较短的代码；））。
我将在这个算法中使用一个常量，我将从其他类中引用它：
public static final int NUMBER_OF_NODES = 50;
然后，我们需要一个edge类来轻松地构造我们的循环，这些循环基本上是边的链表：
public class Edge
{
int u, v;
Edge prev, next;
public Edge(int u, int v)
{
this.u = u;
this.v = v;
}
/**
* Attaches a new edge to this edge, leading to the given node
* and returns the newly created Edge. The node where the
* attached edge starts doesn't need to be given, as it will
* always be the node where this edge ends.
*
* @param node The node where the attached edge ends.
*/
public Edge attach(int node)
{
next = new Edge(this.v, node);
next.prev = this;
return next;
}
}
然后，我们需要一个循环类，它可以很容易地连接两个循环：
public class Cycle
{
Edge start;
boolean[] used = new boolean[NUMBER_OF_NODES+1];
public Cycle(Edge start)
{
// Store the cycle itself
this.start = start;
// And memorize which nodes are being used in this cycle
used[start.u] = true;
for (Edge e = start.next; e != start; e = e.next)
used[e.u] = true;
}
/**
* Checks if this cycle can join with the given cycle. That is
* the case if and only if both cycles use a common node.
*
* @return {@code true} if this and that cycle can be joined,
* {@code false} otherwise.
*/
public boolean canJoin(Cycle that)
{
// Find a commonly used node
for (int node = 1; node <= NUMBER_OF_NODES; node++)
if (this.used[node] && that.used[node])
return true;
return false;
}
/**
* Joins the given cycle to this cycle. Both cycles will be broken
* at a common node and the paths will then be connected to each
* other. The given cycle should not be used after this call, as the
* list of used nodes is most probably invalidated, only this cycle
* will be updated and remains valid.
*
* @param that The cycle to be joined to this cycle.
*/
public void join(Cycle that)
{
// Find the node where we'll join the two cycles
int junction = 1;
while (!this.used[junction] || !that.used[junction])
junction++;
// Find the join place in this cycle
Edge joinAfterEdge = this.start;
while (joinAfterEdge.v != junction)
joinAfterEdge = joinAfterEdge.next;
// Find the join place in that cycle
Edge joinBeforeEdge = that.start;
while (joinBeforeEdge.u != junction)
joinBeforeEdge = joinBeforeEdge.next;
// Connect them together
joinAfterEdge.next.prev = joinBeforeEdge.prev;
joinBeforeEdge.prev.next = joinAfterEdge.next;
joinAfterEdge.next = joinBeforeEdge;
joinBeforeEdge.prev = joinAfterEdge;
// Update the used nodes
for (int node = 1; node <= NUMBER_OF_NODES; node++)
this.used[node] |= that.used[node];
}
@Override
public String toString()
{
StringBuilder s = new StringBuilder();
s.append(start.u).append(" ").append(start.v);
for (Edge curr = start.next; curr != start; curr = curr.next)
s.append("\n").append(curr.u).append(" ").append(curr.v);
return s.toString();
}
}
现在我们的实用程序类已经就位，我们可以编写实际的算法（尽管技术上，算法的一部分是扩展路径（
Edge.attach(int node)）和连接两个循环（Cycle.join(Cycle that)）。/**
* @param edges A variant of an adjacency matrix: the number in edges[i][j]
* indicates how many links there are between node i and node j. Note
* that this means that every edge contributes two times in this
* matrix: one time from i to j and one time from j to i. This is
* also true in the case of a loop: the link still contributes in two
* ways, from i to j and from j to i, even though i == j.
*/
public static Cycle solve(int[][] edges)
{
Deque<Cycle> cycles = new LinkedList<Cycle>();
// First, find a place where we can start a new cycle
for (int u = 1; u <= NUMBER_OF_NODES; u++)
for (int v = 1; v <= NUMBER_OF_NODES; v++)
if (edges[u][v] > 0)
{
// The new cycle starts at the edge from u to v
Edge first, last = first = new Edge(u, v);
edges[last.u][last.v]--;
edges[last.v][last.u]--;
int curr = last.v;
// Extend the list of edges until we're back at the start
search: while (curr != u)
{
// Find any edge that extends the last edge
for (int next = 1; next <= NUMBER_OF_NODES; next++)
if (edges[curr][next] > 0)
{
// We found an edge, attach it to the last one
last = last.attach(next);
edges[last.u][last.v]--;
edges[last.v][last.u]--;
curr = next;
continue search;
}
// We can't form a cycle anymore, which
// means there is no Eulerian cycle.
return null;
}
// Connect the end to the start
last.next = first;
first.prev = last;
// Save it
cycles.add(new Cycle(last));
// And don't forget about the possibility that there are
// more edges running from u to v, so v should be
// re-examined in the next iteration.
v--;
}
// Now we have put all edges into cycles,
// we join them all together (if possible)
merge: while (cycles.size() > 1)
{
// Join the last cycle with any of the previous ones
Cycle last = cycles.removeLast();
for (Cycle curr : cycles)
if (curr.canJoin(last))
{
// Found one! Just join it and continue the merge
curr.join(last);
continue merge;
}
// No compatible cycle found, meaning there is no Eulerian cycle
return null;
}
return cycles.getFirst();
}