先将混合图中的无向图定向，然后统计每个点的入度和出度
有向图存在欧拉回路的充要条件是：所有点的入度等于出度
则出度大于入度的点需要减少出度，出度小于入度的点需要增加出度，改变出度的方法是将边反向，
将边反向的操作相当于将出度“运送”到下一个点，所以问题相当于将多余的出度运送到缺少的出度
将源点连接所有剩余出度的点，容量为 ((out[i] - in[i])/2), 缺少出度的点连接汇点, 容量为 ((in[i] - out[i])/2)
所有定向后的无向边相连，容量为 (1)，如果有流量流过表示将该边反向
最后建出新图后求出欧拉回路即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
const int INF = 1000000007;
int T, n, m;
int u[maxn], v[maxn], dir[maxn], rev[maxn];
int in[maxn], out[maxn];
int h[maxn], cnt = 1;
struct E{
int to, cap, next;
int id;
}e[maxn * 100];
void add(int u, int v, int c, int id){
e[++cnt].to = v;
e[cnt].cap = c;
e[cnt].id = id; // 边的编号
e[cnt].next = h[u];
h[u] = cnt;
}
int s,t;
int vis[maxn], d[maxn], cur[maxn];
bool BFS() {
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = 1;
d[s] = 0;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = h[u]; i != -1 ; i = e[i].next) {
if(!vis[e[i].to] && e[i].cap) {
vis[e[i].to] = 1;
d[e[i].to] = d[u] + 1;
Q.push(e[i].to);
}
}
}
return vis[t];
}
int DFS(int x, int a) {
if(x == t || a == 0) return a;
int flow = 0, f;
for(int &i = cur[x]; i != -1 ; i = e[i].next) {
if(d[x] + 1 == d[e[i].to] && (f = DFS(e[i].to, min(a, e[i].cap))) > 0) {
e[i].cap -= f;
e[i^1].cap += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow() {
int flow = 0;
while(BFS()) {
memcpy(cur, h, sizeof(h));
flow += DFS(s, INF);
}
return flow;
}
vector<int> path;
int vi[maxn * 100];
void euler(int u){
for(int i = h[u] ; i != -1 ; i = e[i].next){
int v = e[i].to;
if(!vi[e[i].id]){
vi[e[i].id] = 1;
euler(e[i].to);
path.push_back(e[i].to);
}
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
scanf("%d", &T);
int fb = 0;
while(T--){
if(fb) printf("
");
fb = 1;
int flag = 0;
memset(h, -1, sizeof(h)); cnt = 1;
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
memset(vi, 0, sizeof(vi));
memset(rev, 0, sizeof(rev));
path.clear();
scanf("%d%d", &n, &m);
char ty[10];
for(int i = 1 ; i <= m ; ++i){
scanf("%d%d", &u[i], &v[i]);
++in[v[i]]; ++out[u[i]];
scanf("%s", ty);
dir[i] = (ty[0] == 'U' ? 0 : 1);
}
s = n + 1, t = n + 2;
int tot = 0;
for(int i = 1 ; i <= n ; ++i){
if(out[i] - in[i] == 0) continue;
if((out[i] - in[i]) & 1) {
flag = 1;
printf("No euler circuit exist
");
break;
} else{
if(out[i] - in[i] > 0){ // 源点向提供出边的点连边
add(s, i, (out[i] - in[i]) / 2, -1);
add(i, s, 0, -1);
tot += (out[i] - in[i]) / 2;
} else{ // 需要出边的点向汇点连边
add(i, t, (in[i] - out[i]) / 2, -1);
add(t, i, 0, -1);
}
}
}
if(flag) continue;
for(int i = 1 ; i <= m ; ++i){
if(!dir[i]){
add(u[i], v[i], 1, i);
add(v[i], u[i], 0, -1);
}
}
int flow = Maxflow();
if(flow == tot){
for(int i = 2 ; i <= cnt ; ++i){
if(e[i].id != -1 && !dir[e[i].id]){
if(e[i].cap == 0) rev[e[i].id] = 1;
}
}
memset(h, -1, sizeof(h)); cnt = 1;
for(int i = 1 ; i <= m ; ++i){
if(dir[i]){
add(u[i], v[i], 0, i);
} else{
if(rev[i]) add(v[i], u[i], 0, i);
else add(u[i], v[i], 0, i);
}
}
euler(1);
printf("1 ");
for(int i = path.size() - 1 ; i >= 0 ; --i){
printf("%d ", path[i]);
}
printf("
");
} else{
printf("No euler circuit exist
");
}
}
return 0;
}