<分区>
我有一个无向图，我需要打印这个图从顶点 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;
}