SGU 101 Domino(欧拉路径)

本文主要是介绍SGU 101 Domino(欧拉路径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0-6作为结点，那么每个骨牌相当于一条无向边了

建图，进行欧拉路径判断，

然后dfs找出路径打印即可

代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;const int N = 7;int n;struct Edge {int u, v, tp, id, vis;Edge() {}Edge(int u, int v, int tp, int id) {this->u = u;this->v = v;this->tp = tp;this->id = id;this->vis = 0;}
}edge[205];int head[N], nxt[205], en;
int deg[N];int judge() {int cnt = 0, v;for (int i = 0; i < 7; i++) if (deg[i]) v = i;for (int i = 0; i < 7; i++) {if (deg[i] % 2) {cnt++;v = i;}}if (cnt == 0 || cnt == 2) return v;return -1;
}int ans[105][2], an;void add_edge(int u, int v, int tp, int id) {edge[en] = Edge(u, v, tp, id);nxt[en] = head[u];head[u] = en++;
}void dfs(int u) {for (int i = head[u]; i + 1; i = nxt[i]) {if (edge[i].vis) continue;edge[i].vis = edge[i^1].vis = 1;dfs(edge[i].v);ans[an][0] = edge[i].id; ans[an][1] = !edge[i].tp; an++;}
}int main() {while (~scanf("%d", &n)) {int u, v;memset(head, -1, sizeof(head));en = 0;memset(deg, 0, sizeof(deg));for (int i = 1; i <= n; i++) {scanf("%d%d", &u, &v);deg[u]++; deg[v]++;add_edge(u, v, 0, i);add_edge(v, u, 1, i);}int s = judge();if (s == -1) printf("No solution\n");else {an = 0;dfs(s);if (an != n) printf("No solution\n");else {for (int i = 0; i < an; i++)printf("%d %c\n", ans[i][0], ans[i][1] == 0 ? '+' : '-');}}}return 0;
}

这篇关于SGU 101 Domino(欧拉路径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---