题目链接
输入a、b、c，表示点a和点b之间有一条边，边序号为c，现在让从第一次输入的两个点中较小的点（这里题意是个坑），走过所有的边后必须回到起点，输出最小路径关键：
欧拉回路+输出路径（边序号）
const int MAXV = 60;
const int MAXE = 2020;
struct Undirect_Euler
{
typedef pair
pii;
int father[MAXV], num[MAXV];
vector
vt[MAXV]; stack
sk; bool vis_edge[MAXE]; set
st; void init() { CLR(vis_edge, 0); while (!sk.empty()) sk.pop(); REP(i, MAXV) { num[i] = 1; father[i] = i; vt[i].clear(); } st.clear(); } int find(int n) { return father[n] == n n : father[n] = find(father[n]); } bool isOne(int ind) { return num[find(ind)] == st.size(); } void merge(int a, int b, int ind) { st.insert(a); st.insert(b); vt[a].push_back(MP(ind, b)); vt[b].push_back(MP(ind, a)); int fa = find(a), fb = find(b); if (fa != fb) { num[fa] += num[fb]; father[fb] = fa; } } // n:判断前n个点是否是一个集合(并查集使用) //是返回true,而且如果是欧拉回路circle = 0,如果是欧拉路circle > 0 //不是返回false bool isEulerRoad(int someone, int& tot, int* ind) { if (!isOne(someone)) return false; tot = 0; REP(i, MAXV) { sort(all(vt[i])); if (vt[i].size() % 2 != 0) { ind[tot++] = i; if (tot > 2) return false; } } return tot == 0 || tot == 2; } //搜索路径,结果保留在sk中 void solve(int n, int ind) { REP(i, vt[n].size()) { int next = vt[n][i].second; int nind = vt[n][i].first; if (!vis_edge[nind]) { vis_edge[nind] = true; solve(next, nind); sk.push(nind); } } } //输出路径,自己写格式 void display() { int t = 0; while (!sk.empty()) { if (t != 0) putchar(' '); printf("%d", sk.top()); t++; sk.pop(); } cout << endl; } } graph; int main() { // freopen("in.txt", "r", stdin); int a, b, c; while (~RII(a, b) && a) { graph.init(); int start = min(a, b); do { RI(c); graph.merge(a, b, c); } while (~RII(a, b) && a); int tot = 0, ind[4]; if (graph.isEulerRoad(start, tot, ind) && tot == 0) { graph.solve(start, -1); graph.display(); } else { puts("Round trip does not exist."); } } return 0; }