Description
Time Limit: 1000 MS Memory Limit: 256 M
给出一幅n个点,m条边的图,分别判断该图是无向图和有向图条件下,是否存在欧拉通路。
输入
输入包含多组数据。第一行为一个整数T(1 ≤ T ≤ 100),代表数据组数,对于每组数据: 第一行是两个整数n和m( 1 ≤ n ≤ 500, 0 ≤ m ≤ n(n − 1)/2 ),分别代表图上点的个数和边的个数。
然后是m行,每行两个整数ui和vi ( 1 ≤ ui, vi ≤ n, ui ≠ vi ),代表图上的一条边所连接的两个点。输入保证没有重边。
输出
首先判断:如果这幅图是无向图,是否存在欧拉通路;
其次判断:如果这幅图是有向图,是否存在欧拉通路。
对于每个判断,如果存在,输出"Yes",否则输出"No"(不包括引号)。两个判断间用空格隔开。
样例输入
3
2 1
1 2
4 3
1 2
1 3
1 4
4 4
1 2
1 3
1 4
2 3
样例输出
Yes Yes
No No
Yes No
Hint
欧拉通路、欧拉回路、欧拉图
无向图:
1) 设 G 是连通无向图,则称经过 G 的每条边一次并且仅一次的路径为欧拉通路;
2) 如果欧拉通路是回路 (起点和终点是同一个顶点), 则称此回路为欧拉回路 (Euler circuit);
3) 具有欧拉回路的无向图 G 称为欧拉图(Euler graph)。
有向图:
1) 设 D 是有向图, D 的基图连通,则称经过 D 的每条边一次并且仅一次的有向路径为有向欧拉通路;
2) 如果有向欧拉通路是有向回路,则称此有向回路为有向欧拉回路(directed Euler circuit);
3) 具有有向欧拉回路的有向图 D 称为有向欧拉图(directed Euler graph)。
Extend
欧拉回路打印路径算法:Fleury(佛罗莱)算法
Author
GooZy
用度数就能做出来
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w",stdout);
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int MAXN=1000+5;
int DU[MAXN];
int IN[MAXN],OUT[MAXN];
int n,m,sz;
int father[MAXN];
void edge_init(){
memset(DU,0,sizeof(DU));
memset(IN,0,sizeof(IN));
memset(OUT,0,sizeof(OUT));
for(int i=1;i<=n;i++){
father[i]=i;
}
}
int Find(int x){
if(x!=father[x]){
father[x]=Find(father[x]);
}
return father[x];
}
int main()
{
//FIN
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
edge_init();
int sum=n;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
DU[u]++;
DU[v]++;
IN[v]++;
OUT[u]++;
int root1=Find(u);
int root2=Find(v);
if(root1!=root2){
father[root2]=root1;
sum--;
}
}
if(sum!=1){
printf("No No\n");
continue;
}
int cnt=0;
for(int i=1;i<=n;i++){
if(DU[i]%2==1) cnt++;
}
if(cnt==0||cnt==2) printf("Yes");
else printf("No");
bool flag=1;
int fir=0, sec=0;
for (int i=1;i<=n;i++) {
if(IN[i]!=OUT[i]){
if(!fir&&IN[i]-OUT[i]==1)fir=1;
else if(!sec&&IN[i]-OUT[i]==-1){
sec=1;
}else{
flag=0;
}
}
}
if (flag) printf(" Yes\n");
else printf(" No\n");
}
return 0;
}