定义
欧拉通路
- 图中行遍所有顶点且恰好经过图中的每条边一次的通路. 顶点可以重复经过，边只经过一次。
欧拉回路
- 图中行遍所有顶点且恰好经过图中的每条边一次的回路. 顶点可以重复经过，边只经过一次。
欧拉图:
- 有欧拉回路的图
半欧拉图
- 有欧拉通路而无欧拉回路的图.
几点说明：
- 上述定义对无向图和有向图都适用.
- 规定平凡图为欧拉图.
平凡图: 1 阶零图，即只有1个顶点没有边的图
- 欧拉通路是简单通路, 欧拉回路是简单回路.
- 环不影响图的欧拉性.
图中,为欧拉图;
为半欧拉图;
既不是欧拉图, 也不是半欧拉图.
判定
无向欧拉图
- 无向图
为欧拉图当且仅当
无向半欧拉图
- 无向图
有向欧拉图
- 有向图
是欧拉图当且仅当
有向半欧拉图
- 有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出度大
(终点), 另一个出度比入度大
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int edge[M][M];
int vis[M];
int du[M];
int n,m;
void init( )
{
memset(edge,0,sizeof(edge));
memset(vis,0,sizeof(vis));
memset(du,0,sizeof(du));
}
void dfs(int x)//判断是否连通
{
vis[x]=1;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&edge[x][i])
{
dfs(i);
}
}
}
int cheak(int n)//查找多少个顶点的度是否是奇数
{
int ans=0;
for(int i=1;i<=n;i++)
{
if(du[i]%2!=0)
{
ans++;
}
}
return ans;
}
int main( )
{
int x,y;
while(~scanf("%d%d",&n,&m)&&n)
{
init( );
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
edge[x][y]=edge[y][x]=1;
du[x]++;
du[y]++;
}
dfs(1);
int flag=1;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
flag=0;
break;
}
}
if(!cheak(n)&&flag)
{
printf("1\n");
}
else
{
printf("0\n");
}
}
return 0;
}
- 每个单词的第一个字母到最后一个字母有一条有向边，构图
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int edge[26][26];
char s[1010];
// int out[26];
// int in[26];
int du[26];
int vis[26];
int use[26];
int n;
void dfs(int x)
{
vis[x]=1;
for(int i=0; i<26; i++)
{
if(edge[x][i]&&!vis[i])
{
dfs(i);
}
}
}
int main( )
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
getchar( );
// memset(out,0,sizeof(out));
// memset(in,0,sizeof(in));
memset(use,0,sizeof(use));
memset(edge,0,sizeof(edge));
memset(du,0,sizeof(du));
while(n--)
{
scanf("%s",s);
getchar( );
int len=strlen(s);
int u=s[0]-'a';
int v=s[len-1]-'a';
edge[u][v]=1;
// out[u]++;
// in[v]++;
du[u]--;//出度为减
du[v]++;//入度为加
use[u]=1;
use[v]=1;
}
int x=-1;
int flag1=0;
int flag2=0;
for(int i=0; i<26; i++)
{
if(!use[i])
{
continue;
}
else if(du[i]==0)
{
if(x==-1)
{
x=i;
}
}
else if(du[i]==-1)
{
flag1++;
x=i;
if(flag1>1)
{
break;
}
}
else if(du[i]==1)
{
flag2++;
if(flag2>1)
{
break;
}
}
else
{
flag1=flag2=-1;
break;
}
// else if(out[i]==in[i])
// {
// if(x==-1)
// {
// x=i;
// }
// }
// else if(out[i]-in[i]==1)
// {
// flag1++;
// x=i;
// if(flag1>1)
// {
// break;
// }
// }
// else if(in[i]-out[i]==1)
// {
// flag2++;
// if(flag2>1)
// {
// break;
// }
// }
// else
// {
// flag1=flag2=-1;
// break;
// }
}
if((flag1==1&&flag2==1)||(flag1==0&&flag2==0))//两者为0,欧拉回路，两者为1,欧拉通路
{
int flag=0;
memset(vis,0,sizeof(vis));
dfs(x);
for(int i=0; i<26; i++)
{
if(!vis[i]&&use[i])
{
flag=1;
break;
}
}
if(flag==1)
{
printf("The door cannot be opened.\n");
}
else
{
printf("Ordering is possible.\n");
}
}
else
{
printf("The door cannot be opened.\n");
}
}
return 0;
}
