日常发癫
好累好累好累好累。。。好烦好烦好烦好烦。。。
欧拉回路
前置概念
度数(出度和入度),对于无向图中一点的度数即为与该点相连的边数。
性质
欧拉回路
无向图
每个点的度数均为偶数。可以想象,如果存在欧拉回路则通过一条边进入某个点时,必然需要从另一条边出来,即进入该点的边数与从该点出来的边数相等,即与该点相连的边数为偶数(度数为偶数)。若某无向图中存在度数不为偶数的点,则该无向图不存在欧拉回路。
有向图
每点的入度数等于出度数。与无向图相同,每次从一条边进入则需要从另一条边出来,与之不同的是有向图的边是有向的,所以需要入度数等于出度数。若某有向图中存在入度数不等于出度数的点,则该图不存在欧拉回路。
欧拉路径
欧拉路径相当于把一个欧拉回路从某个点剪开,形成一条路径,所以可以允许存在一个点作为起点,一个点作为终点,这两个点的入度数与出度数的差的绝对值可以为一(起点可以少进入一次,终点可以少出来一次)。
有向图
从起点开始,因此起点可以少进入一次,即起点的入度数可以比出度数少一;到终点即结束,因此终点可以少出来一次,即终点的出度数可以比入度数少一。只能存在两个点(或不存在任何一个点)的入度数与出度数的差的绝对值为一(不能超过一),其中一个(入度数小于出度数)作为起点,另一个(出度数小于入度数)作为终点。否则不存在欧拉路径。
无向图
与有向图相同,起点可以少进入一次,终点可以少出来一次,与有向图不同的是无向图中边是双向的,所以度数为奇数的两个点可以作为起点和终点,若度数为奇数的点为0或2则存在欧拉路径,否则不存在。
思想
深度优先搜索的思想,通过遍历图中的边来找到欧拉回路。
1.选择一个起点,遍历该点连接的边,并将该点添加到欧拉回路中。
2.若该顶点还有未访问的边,则选择一条未访问的边,并将选择该边对应的另一个点。
3.遍历该点的边,继续选择未访问的边对应的点。
4.重复步骤2和步骤3,直到访问完所有边。
代码实现
欧拉回路
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e3 + 5; int book[N][N]; int idn[N], out[N]; vector<int> ans; void dfs(int x, int n) { for (int i = 1; i <= n; i++) { //可能存在两个点之间存在多条边 if (book[x][i] > 0) { book[x][i]--; //无向图 book[i][x]--; dfs(i, n); } } //存入路径 ans.push_back(x); } signed main() { int n, m; cin>>n>>m; for (int i = 1; i <= m; i++) { int u, v; cin>>u>>v; book[u][v]++; idn[u]++; out[v]++; //无向图 book[v][u]++; idn[v]++; out[u]++; } for (int i = 1; i <= n; i++) { if (idn[i] & 1) { cout<<"不存在欧拉回路"; return 0; } } //这里从点1开始,因为是欧拉回路,所以其实从哪个点开始都可以 dfs(1, n); int len = ans.size(); for (int i = len - 1; i >= 0; i--) { //逆向输出 cout<<ans[i]<<" "; } return 0; }
欧拉路径
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 const int N = 1e3 + 5; 5 int book[N][N]; 6 int idn[N], out[N]; 7 vector<int> ans; 8 void dfs(int x, int n) { 9 for (int i = 1; i <= n; i++) { 10 //可能存在两个点之间存在多条边 11 if (book[x][i] > 0) { 12 book[x][i]--; 13 //无向图 14 book[i][x]--; 15 dfs(i, n); 16 } 17 } 18 //存入路径 19 ans.push_back(x); 20 } 21 signed main() { 22 int n, m; 23 cin>>n>>m; 24 for (int i = 1; i <= m; i++) { 25 int u, v; 26 cin>>u>>v; 27 book[u][v]++; 28 idn[u]++; 29 out[v]++; 30 //无向图 31 book[v][u]++; 32 idn[v]++; 33 out[u]++; 34 } 35 int head = 0; 36 int cnt = 0; 37 //查找度数为奇数点的个数 38 for (int i = 1; i <= n; i++) { 39 if (idn[i] & 1) { 40 cnt++; 41 //一般会要求按字典序输出,所以找到第一个度数为奇数的作为起点 42 if (head == 0) 43 head = i; 44 } 45 } 46 if (cnt != 0 && cnt != 2) { 47 cout<<"不存在欧拉路径"; 48 return 0; 49 } 50 //全为偶数则可以把任何一个点作为起点 51 if (head == 0) 52 head = 1; 53 dfs(head, n); 54 int len = ans.size(); 55 for (int i = len - 1; i >= 0; i--) { 56 //逆向输出 57 cout<<ans[i]<<" "; 58 } 59 return 0; 60 }标签:度数,int,++,book,回路,欧拉 From: https://www.cnblogs.com/tunecoming/p/17488762.html