欧拉图
概念
定义
欧拉回路：图中经过每条边一次且仅一次的环；
欧拉路径：图中经过每条边一次且仅一次的路径；
欧拉图：有至少一个欧拉回路的图；
半欧拉图：没有欧拉环，但有至少一条欧拉路径的图。
无向图判定条件
- 图是联通的（度数为0的点不用考虑，因为是孤立的点，没影响）～先决条件
- 所有点的度数都是偶数～存在欧拉回路，欧拉图
- 有且仅有两个点的度数是奇数～存在欧拉路径，半欧拉图
两个奇数度数的点一个是路径起点一个是路径终点
证明：因为任意一个点，欧拉环（或欧拉路径）从它这里进去多少次就要出来多少次，故(进去的次数+出来的次数)为偶数，又因为(进去的次数+出来的次数)=该点的度数（根据定义），所以该点的度数为偶数。
有向图判定条件
- 把所有的边强行改为无向边之后（这个图叫原图的基图），联通～先决条件
- 所有点出度等于入度～存在欧拉回路，欧拉图
- 有且仅有两个点出度不等于入度，一个出度比入度大1，另一个入度比出度大1～欧拉路径，半欧拉图
出度比入度大1的点是路径起点，入度比出度大1的点是路径终点
证明：与无向图证明类似，一个点进去多少次就要出来多少次。
模板
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
struct Graph{ int head[MAXN]; int nxt[MAXE]; int ind[MAXN]; int outd[MAXN]; int from[MAXE]; int end[MAXE]; int vis[MAXE]; int q; int V,E; inline void addEdge(int _from,int _to){ from[q] = _from; end[q] = _to; outd[_from]++; ind[_to]++; nxt[q] = head[_from]; head[_from] = q++; } inline void clear(){ q = 1; memset(head, 0, sizeof(head)); memset(nxt, 0, sizeof(nxt)); memset(end, 0, sizeof(end)); memset(vis, false, sizeof(vis)); memset(from, 0, sizeof(from)); memset(ind, 0, sizeof(ind)); memset(outd, 0, sizeof(outd)); } }; stack<int> res; void euler_dfs(Graph &g,int cur){ for (int i = g.head[cur]; i; i = g.nxt[i]) { if (!g.vis[i]) { g.vis[i] = true; //g.vis[i^1] = true; 无向图的时候，取消这句注释 euler_dfs(g,g.end[i]); res.push(i); } } } vector<int> singular; int euler_judge(Graph &g){ singular.clear(); for (int i = 1; i <= g.V; i++) { if (g.ind[i] != g.outd[i]) { singular.push_back(i); } } if (singular.size() == 2) { if(g.ind[singular[0]] == g.outd[singular[0]] + 1){ swap(singular[0],singular[1]); } if(g.ind[singular[0]] + 1 == g.outd[singular[0]] && g.outd[singular[1]] + 1 == g.ind[singular[1]]){ return 1; } return 0;//euler path //判断必须严格，差一点也不行，跑出合适个数的结果都可能是错的！ }else if(singular.size() == 0){ for (int i = 1; i<= g.V; i++) { if (g.ind[i]) { singular.push_back(i); } } return 2;//euler loop }else{ return 0;//failed } } //singular[0]是起点 |