uva 10735 混合图欧拉路径的判定，方案输出。(二)
[u]=tot++; } void dfs(int u){ for(int i=Head[u];i!=-1;i=Edge[i].next){ NODE &e=Edge[i]; if(!e.vis){ e.vis=1; dfs(e.to); } } ans[top++]=u; } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int n,m,T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head));tol=0; memset(Head,-1,sizeof(Head));tot=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); char op[10]; while(m--){ int u,v; scanf("%d%d%s",&u,&v,op); if(op[0]=='D')add(u,v); else addedge(u,v,1); out[u]++;in[v]++; } int flag=1,sum=0; for(int i=1;i<=n;i++){ if((out[i]+in[i])%2){ flag=0;break; } if(out[i]>in[i])sum+=(out[i]-in[i])/2,addedge(0,i,(out[i]-in[i])/2); else if(in[i]>out[i])addedge(i,n+1,(in[i]-out[i])/2); } if(!flag||sap(0,n+1,n+10)!=sum)puts("No euler circuit exist"); else{ top=0; for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=edge[j].next){ int v=edge[j].to; if(v>=1&&v<=n&&edge[j].cap>0) add(i,v); } top=0; dfs(1); for (int i = top-1; i >= 0; i --) printf("%d%c",ans[i],i==0 '\n':' '); } if (T) puts(""); } return 0; }