DAY1:
上午：
引入：
对任意两个元素a，b之间关系（a，b）的取值仅为 True 或者 False，可以考虑使用图来抽象。这样我们称一个元素 a 为一个结点，（a，b）== True 则称结点 a，b 间有连边，否则 a，b 间没有连边。
问题转化：一张奇数个点的图 G，证明存在一个点度数为偶数。
转化为更强的问题为：给定一张奇数个点的图 G，证明度数为偶数的点的个数为奇数。
（相反的问题：给定一张奇数个点的图 G，证明度数为奇数的结点的个数为偶数。）
证明：考虑所有点的度数和，由于一条边会被计算到两个结点的度数上，故其必定为偶数。（小学数学易得结论？）
Ex.1：首先可证 n-1 个点与除它之外 n-2 个点连边所以可连 (n-1)(n-2)/2 条边，因此可得 n 个点和至少 ((n-1)(n-2)/2)+1 条边的图是连通图。
Ex.2：
由图可得，对于任意一个图，可将其分为若干个连通块，连通块内部各点都相连，因此其补图原来的连通块内各点于其他各连通块各点相连，因此一定是联通的。
Ex.3：
任意两边至少有一个点是重合的，即为如图：
因此当为完全图时，每点度数>=2，因此不可能为星星，反之亦然。
Ex.4：***
Ex.5：分类讨论，
当存在度数为一的点时，删掉度数为一的点剩下的图依旧是连通图。
当不存在时，选择任意一点为起点，计算其他点与起点的距离，删掉距离起点最远的点后，图依旧为连通图。
欧拉回路和哈密顿回路：
1）考虑一个度数为奇数的点，因为它的所有邻边均要遍历恰好一次，故其必须为欧
拉路径的起点或终点。因此可以立即推出，一张存在欧拉路径的图恰好有两个度数为奇数
的点，存在欧拉回路的图没有度数为奇数的点。
2）任意两个回路，可以拼成一个大的回路。
由这两个观察可以发现，Fact 1是存在欧拉路径或者欧拉回路的充要条件。
反证法，假设没有哈密顿回路。
我们由图 G 构造出一个新的没有哈密顿回路的图 G'，具体的，令 G'=G，对于每条不在图 G 中的边，如果加入 G' 后不会产生哈密顿回路，则加入，该构造的顺序不重要。
此时我们得到了一个图 G'，再加入任何一条边都会得到一条哈密顿回路，并且由于我们仅加入了新的边，所有结点的度数任然大于等于 n/2。
假设 (v1，vn) 这条边不在 G' 中，我们知道必定存在一条哈密顿路径 v1，v2，...，vn 考虑 (v1，vi) 有一条边，则 (vi-1，vn) 必定不能有边，否则可以构造出一条哈密顿回路。
因为这样的 vi 至少有 n/2 个，从而这样的 vi-1 也至少有 n/2 个，又由于 vn 不能和自己连边，故而它至多与 n-n/2-1 个点连边，<=n/2 ，因此与定理矛盾，因此假设不成立。
Ex.6：因为两数互质，因此间隔至少为2，又因为有 n+1，个小于等于 2n 的正整数，所以显然，存在两个数互质。
Ex.7：...
Ex.8：将棋盘进行黑白染色和蓝红染色
Ex.9：Luogu P1341
1 //By:Komorebi_03
2 #include<bits/stdc++.h>
3 using namespace std;
4 #define clear(a) memset(a,0,sizeof a)
5 #define ll long long
6 const int N = 1e3+5;
7 int n,sum,dis[N][N];
8 char in[N],a[N];
9 inline int read()
10 {
11 int x=0,f=1;char ch=getchar();
12 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
13 while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
14 return x*f;
15 }
16
17 void Find(int i)
18 {
19 for (int j=1;j<=150;j++)
20 {
21 if(dis[i][j]>0)
22 {
23 dis[i][j]--;
24 dis[j][i]--;
25 Find(j);
26 }
27 }
28 a[++sum]=i;
29 return ;
30 }
31
32 int main()
33 {
34 n=read();
35 for (int i=1;i<=n;i++)
36 {
37 string s;
38 cin>>s;
39 dis[s[0]][s[1]]++;
40 dis[s[1]][s[0]]++;
41 in[s[0]]++;
42 in[s[1]]++;
43 }
44 int h=0;
45 int cnt=0;
46 for (int i=1;i<=150;i++)
47 {
48 if(in[i] & 1)
49 {
50 cnt++;
51 if(!h)
52 h=i;
53 }
54 }
55 if(!h)
56 {
57 for (int i=0;i<150;i++)
58 {
59 if(in[i])
60 {
61 h=i;
62 break;
63 }
64 }
65 }
66 if(cnt && cnt!=2)
67 {
68 cout<<"No Solution";
69 exit(0);
70 }
71 Find(h);
72 if(sum<n+1)
73 {
74 cout<<"No Solution";
75 exit(0);
76 }
77 for(int i=sum;i>=1;i--)
78 cout<<a[i];
79 return 0;
80 //Amireux_35
81 }
P1341
图的储存和遍历：
标签：度数,个点,哈密顿,奇数,int,2023,回路,外出,五一 From： https://www.cnblogs.com/G7526122/p/17365793.html