luogu P2731 骑马修栅栏 Riding the Fences https://www.luogu.org/problemnew/show/P2731
luogu P1341 无序字母对 https://www.luogu.org/problemnew/show/P1341
度数: 一个点上连接边的个数
1. 欧拉道路: 相当于一笔画
无向图: 除了两个或没有点为奇点 (度数为奇) 以外, 其余度数均为偶
有向图: 只有两个点或没有点入度不等于出度, 起点入度 = 出度 - 1, 终点入度 = 出度 + 1
2. 欧拉回路:
无向图: 奇点个数为 0
有向图: 所有点出度 = 入度(起点终点重合)
- #include<cstdio>
- #include<iostream>
- using namespace std;
- const int maxn=2500;
- int f,head[maxn],nxt[maxn],to[maxn],du[maxn],cnt=-1,t,zhan[maxn],vis[maxn];
- void add(int a,int b)
- {
- cnt++;
- nxt[cnt]=head[a];
- to[cnt]=b;
- head[a]=cnt;
- }
- void dfs(int k)
- {
- while(du[k])
- {
- int mi=2e9,tomi=2e9;
- for(int i=head[k];i!=-1;i=nxt[i])
- {
- if(!vis[i]&&to[i]<tomi) mi=i,tomi=to[i]; // 题中要求存在多组解的情况下, 输出进制表示法中最小的一个
- }
- vis[mi]=1;
- vis[mi^1]=1;
- du[k]--;
- du[tomi]--;
- dfs(tomi);
- zhan[++t]=tomi;
- }
- }
- int main()
- {
- scanf("%d",&f);
- int a,b,minn=2e9;
- for(int i=0;i<1050;i++) head[i]=-1;
- for(int i=1;i<=f;i++)
- {
- scanf("%d%d",&a,&b);
- add(a,b);
- add(b,a);
- du[a]++;
- du[b]++;
- minn=min(min(a,b),minn);
- }
- for(int i=1;i<=f;i++)
- {
- if(du[i]%2==1)
- {
- minn=i;
- break;
- }
- }
- dfs(minn);
- printf("%d\n",minn);
- for(int i=t;i>0;i--) printf("%d\n",zhan[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2930470.html