打印Euler路径

Question

我得到了一个无向图，我需要打印这个图从顶点A到顶点B的欧拉路径。我的算法是这样的:首先，我使用Tarjan算法找到所有作为桥的边。然后，从顶点A开始，从每个顶点我选择他的一条边，试着不烧桥，也就是说，如果我可以选择不是桥的边，我会选择它们。然而，这个解决方案只给了我30/100分的问题。我还发现了一个O((N+M)^2)解决方案，它工作得很好，但由于N和M非常大，我需要一些线性的解决方案。

下面是我的代码，你有什么建议吗？

int N, M, A, B, c, dfs_low[MAX_N], dfs_num[MAX_N], dfs_parent[MAX_N],articulation_vertex[MAX_N];
int dfsNumberCounter = 1, dfsRoot, rootChildren;
vii g[MAX_N];

void articulationPointAndBridge(int u) {
  dfs_low[u] = dfs_num[u] = dfsNumberCounter++;     // dfs_low[u] <= dfs_num[u]
  for (int j = 0; j < (int)g[u].size(); j++) {
    ii v = g[u][j];
    if (dfs_num[v.first] == DFS_WHITE) {                          // a tree edge
      dfs_parent[v.first] = u;
      if (u == dfsRoot) rootChildren++;  // special case, count children of root
      articulationPointAndBridge(v.first);
      if (dfs_low[v.first] > dfs_num[u]){                           // for bridge
        g[u][j].second = 2;
        for(int i=0;i<g[v.first].size();i++)
            if(g[v.first][i].first == u && g[v.first][i].second){
                g[v.first][i].second = 2;
                break;
            }
       }
      dfs_low[u] = min(dfs_low[u], dfs_low[v.first]);       // update dfs_low[u]
    }
    else if (v.first != dfs_parent[u])       // a back edge and not direct cycle
      dfs_low[u] = min(dfs_low[u], dfs_num[v.first]);       // update dfs_low[u]
} }

void EulPath(int u){ 
    int idx = -1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i].second == 1){
            idx = i;
            break;
        }

    if(idx == -1)
        for(int j=0;j<g[u].size();j++)
            if(g[u][j].second){
                idx = j;
                break;
            }
    if(idx != -1){
        int v = g[u][idx].first;
        out<<u+1<<" "<<v+1<<endl;
        g[u][idx].second=0;
        for(int j=0;j<g[v].size();j++)
            if(g[v][j].first == u && g[v][j].second){
                g[v][j].second = 0;
                break;
            }
        EulPath(v);
    }

}





int main() {
    //in = fopen("input.txt","r"); out = fopen("output.txt","w");
    in.open("input.txt"); out.open("output.txt");

    //fscanf(in, "%d %d %d %d" , &N, &M, &A, &B);
    in>>N>>M>>A>>B;
    for(int i=0;i<M;i++){
        int t,t2;
        //fscanf(in, "%d %d", &t, &t2);
        in>>t>>t2; t--; t2--;
        g[t].pb(ii(t2,1));
        g[t2].pb(ii(t,1));
    }
    articulationPointAndBridge(A-1);
    /*for(int i=0;i<N;i++)
        for(int j=0;j<g[i].size();j++)
            cout << i <<" "<<g[i][j].first<<" "<<g[i][j].second<<endl;
            cin>>N;*/
    EulPath(A-1);

    in.close(); out.close();
    //fclose(in); fclose(out);
    return 0;
}

Answer 1

我会考虑实现Hierholzer的算法。(例如，请参见http://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm)。无需预先检测网桥。