sgu101 欧拉路
- sgu101 欧拉路 推荐度：
- 相关推荐
sgu101 欧拉路
简略题意：给出n个多米诺骨牌，每个牌正面反面有不同的数字，一个牌 i i 能连在另一个牌
可以把多米诺骨牌的看做边，两侧的数字看做节点，那么就可以转化成一个无向图欧拉路问题。
需要注意一下：
1. 判定无解
2. 判定图是否连通#define others
#ifdef poj
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#endif // poj
#ifdef others
#include <bits/stdc++.h>
#endif // others
//#define file
#define all(x) x.begin(), x.end()
using namespace std;
const double eps = 1e-8;
int dcmp(double x) { if(fabs(x)<=eps) return 0; return (x>0)?1:-1;};
typedef long long LL;namespace solver {const int maxn = 300;int n;struct Edge {int u, v, next, type, vis, id;void print() {if(type == 0)printf("%d %c\n", id, '+');elseprintf("%d %c\n", id, '-');}} edge[maxn<<1];int deg[maxn], head[maxn], eg = 0;void init() {eg = 0;memset(head, -1, sizeof head);}void add(int u, int v, int id) {edge[eg] = {u, v, head[u], 0, 0, id}, head[u] = eg++;swap(u, v);edge[eg] = {u, v, head[u], 1, 0, id}, head[u] = eg++;}vector<int> res;void dfs(int u) {for(int i = head[u]; ~i; i = edge[i].next) {if(!edge[i].vis && !edge[i^1].vis) {edge[i].vis = edge[i^1].vis = 1;dfs(edge[i].v);res.push_back(i);}
// if(i == -1) break;}}void solve() {init();scanf("%d", &n);int st = 1, cnt = 0;for(int i = 1; i <= n; i++) {int u, v;scanf("%d%d", &u, &v);deg[u]++, deg[v]++;st = u;add(u, v, i);}for(int i = 0; i <= 6; i++) {if(deg[i] & 1) cnt++, st = i;}if(cnt != 0 && cnt != 2) puts("No solution");else {dfs(st);reverse(all(res));if(res.size() < n) puts("No solution");else {for(int i = 0; i < res.size(); i++) {int id = res[i];edge[id].print();}}}}
}int main() {
#ifdef filefreopen("gangsters.in", "r", stdin);freopen("gangsters.out", "w", stdout);
#endif // file
// int t;
// scanf("%lld", &t);
// while(t--)solver::solve();return 0;
}