比较容易理解；
无向图：
第一步：判断是否联通，并查集解决；
第二步：判断是否有度数为奇数的点，有的话构成不了欧拉回路；
有向图：
记录度数，出的话+1，入的话-1；
第一步：判断是否联通，并查集解决；
第二步：只有一个点度数1，一个点度数-1，其他为0，否则构不成欧拉回路；
主要是能看出来这个用欧拉回路解决吧；
欧拉回路
板题；无向图；
#include<bits/stdc++.h> using namespace std; #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i--) #define pb push_back #define pf push_front #define fi first #define se second 11 typedef long long ll; typedef unsigned long long ull; typedef long double ldb; typedef double db; const ll INF=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f;//0x7fffffff; const double eps=1e-9; const ll MOD=9999991; const int maxn=1e3+5; vector<int>e[maxn]; int n,m; int degree[maxn]; int fa[maxn]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void build(int x,int y){int dx=find(x),dy=find(y);if(dx!=dy)fa[dx]=dy;} int main(){ while(~scanf("%d %d",&n,&m),n){ for(int i=0;i<=n;i++)degree[i]=0,fa[i]=i,e[i].clear(); while(m--){ int u,v; scanf("%d %d",&u,&v); degree[u]++; degree[v]++; e[u].pb(v); e[v].pb(u); build(u,v); } bool ok=1; for(int i=1;i<=n;i++){ if(degree[i]%2==1||find(i)!=find(1)){ ok=0; break; } } cout<<ok<<endl; } return 0; }
Play on Words
HDU - 1116题意：成语接龙；
解法：有向图欧拉回路，并查集判断联通，最后检查一下每个点，看看能不能构成欧拉路或者欧拉回路；
#include<bits/stdc++.h> using namespace std; #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i--) #define pb push_back #define pf push_front #define fi first #define se second 11 typedef long long ll; typedef unsigned long long ull; typedef long double ldb; typedef double db; const ll INF=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f;//0x7fffffff; const double eps=1e-9; const ll MOD=9999991; const int maxn=1e3+5; int n,m; int fa[maxn]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void build(int x,int y){int dx=find(x),dy=find(y);if(dx!=dy)fa[dx]=dy;} int in[30],out[30]; int main(){ int n,t; cin>>t; while(t--){ scanf("%d",&n); rep(i,0,30)fa[i]=i; // rep(i,0,n) memset(in,0,sizeof in); memset(out,0,sizeof out); string word; rep(i,1,n){ cin>>word; int u=word[0]-'a'; int v=word[word.size()-1]-'a'; out[u]++; in[v]++; build(u,v); } bool ok=1; int st=0,s=0,e=0,cnt=0,nor=0; for(int i=0;i<26;i++){ if(in[i]==0&&out[i]==0)continue; cnt++; if(fa[i]==i)st++; if(in[i]-out[i]==1)e++; if(out[i]-in[i]==1)s++; if(out[i]==in[i])nor++; } if(st==1&&(nor==cnt||nor==cnt-2&&s==1&&e==1))ok=1; else ok=0; // vector<int>e[maxn]; // cout<<"test "<<cnt<<" "<<st<<" "<<s<<" "<<e<<" "<<nor<<endl; if(ok)cout<<"Ordering is possible."<<endl; else cout<<"The door cannot be opened."<<endl; } return 0; }
The Best Path
题意：给你一个无向连通图，问你能不能构成欧拉路，如果能，求ai的最大异或和，
解法：先判断，是欧拉路，每次每个节点的异或次数就是度数除2，因为一进一出，
如果是欧拉回路，还要枚举起点，因为起点还会再回来一次。
#include<bits/stdc++.h> using namespace std; #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i--) #define pb push_back #define pf push_front #define fi first #define se second 11 typedef long long ll; typedef unsigned long long ull; typedef long double ldb; typedef double db; const db PI=acos(-1.0); const ll INF=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f;//0x7fffffff; const double eps=1e-9; const ll MOD=9999991; const int maxn=1e5+5; // ll sum[maxn],f[maxn]; int a[maxn],degree[maxn]; int main(){ int t,n,m; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)degree[i]=0; rep(i,1,n)scanf("%d",&a[i]); while(m--){ int u,v; scanf("%d %d",&u,&v); degree[u]++; degree[v]++; } int cnt=0,ans=0; for(int i=1;i<=n;i++){ if(degree[i]&1)cnt++; } if(cnt!=0&&cnt!=2){ cout<<"Impossible"<<endl; continue; } for(int i=1;i<=n;i++){ degree[i]=(degree[i]+1)>>1; if(degree[i]&1)ans^=a[i]; } int tmp=0; if(cnt==0){ for(int i=1;i<=n;i++){ tmp=max(tmp,ans^a[i]); } ans=tmp; } cout<<ans<<endl; } // system("pause"); return 0; }