欧拉路和欧拉回路
欧拉路
经过图中所有边恰好一次的通路就被称为欧拉通路或者欧拉路
感觉这一块的算法会用到dfs
欧拉回路
经过图中所有边恰好一次的回路可以被称为欧拉回路
无向图
对于无向图G，G中存在欧拉回路当且仅当G中所有度非0的点都是联通的，且没有奇数度数的点
这里科普一下什么是度:包括一个点的入度和出度，但是因为是无向图，路线是没有方向的，这里参考一下离散数学的知识点
对于无向图G，G中存在欧拉路当且仅当G中所有度非0的点都是联通的，且G中恰好有0个或者两个奇数度数的点（0表示欧拉回路）
有向图
对于有向图G，G中存在欧拉回路当且仅当G中所有度非0的点都是强连通的，并且每个点的入度和出度相同。
什么是强连通呢？就是任意一个点可以到另一个点（度都是非0）
对于有向图G，G中存在欧拉路当且仅当：
1.将G中的所有有向边全部改为无向边后，G中所有度非0的点都是联通的
2.最多只有一个点的出度减去入度为1
3.最多只有一个点的入度减去出度为1
4.其他点的入度等于出度
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int f[N];
int c[N];
int l;
int v[N];
int ind[N],outd[N];
std::vector<int> g[N];
inline void dfs(int x){
while(f[x]<v[x]){
//这里我们避免了重复使用节点
int y=g[x][f[x]];
f[x]++;
dfs(y);
c[++l]=y;
}
}
inline void Euler(){
int x=0;
int y=0;
int z=0;
for(int i=1;i<=n;i++){
if(outd[i]==ind[i]+1){
y++;
x=i;
//记录出度大于入度的个数
}
if(outd[i]!=ind[i]){
z++;
}
}
if(!(!z||(y==1&&z==2))){
cout<<"No"<<endl;
//这就没有办法构成
return ;
}
if((!x)){
for(int i=1;i<=n;i++){
if(ind[i]){
x=i;
cout<<i<<endl;
}
}
}
memset(f,0,sizeof f);
l=0;
dfs(x);
c[++l]=x;
if(l==m+1){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
for(int i=l;i;i--){
cout<<c[i]<<" ";
}
cout<<endl;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
g[x].emplace_back(y);
v[x]++;//记录一下x连出去的边数
outd[x]++;
ind[y]++;
//这里记录一下入度和出度
}
// for(int i=1;i<=n;i++){
// cout<<ind[i]<<" "<<outd[i]<<endl;
// }
Euler();//判断存不存在欧拉路
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
无向图欧拉路
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct Node
{
int x,y;
Node(int _x,int _y){
x=_x;
y=_y;
};//这是一个构造函数
};
int n,m;
std::vector<Node> g[N];
int d[N];//无向图不分出度和入度
int v[N];
int f[N];
int c[N];
bool b[N];
int cnt=1;
int l=0;
inline void dfs(int x){
while(f[x]<v[x]){
int y=g[x][f[x]].x;
int idx=g[x][f[x]].y;
if(!b[idx]){
++f[x];
b[idx]=b[idx^1]=true;//这条边和对应反向的那条边都不可以用了
dfs(y);
c[++l]=y;
}
else{
++f[x];
}
}
}
inline void Euler(){
int x=0,y=0;
for(int i=1;i<=n;i++){
if(d[i]&1){
y++;
x=i;
//这里判断度数是不是奇数
}
}
if(y&&y!=2){
cout<<"No"<<endl;
return ;
}
if(!x){
for(int i=1;i<=n;i++){
if(d[i]){
x=i;
}
}
}
memset(b,false,sizeof b);
memset(f,0,sizeof f);
l=0;
dfs(x);
c[++l]=x;
if(l==m+1){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
return ;
}
for(int i=1;i<=n;i++){
cout<<c[i]<<" ";
}
return ;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
g[x].push_back(Node(y,++cnt));
g[y].push_back(Node(x,++cnt));
d[x]++;
d[y]++;
v[x]++;
v[y]++;
}
Euler();
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}