1.基本概念：
图G为连通图，若图G中存在一条路径经过每条边一次且仅一次，那么这条路径为欧拉路，若这条路径的起点与终点相同，那么为欧拉回路。欧拉回路是欧拉路的特例。
存在欧拉回路的图称为欧拉图。欧拉路以及欧拉回路常用于解决一笔画问题。
2.判定条件。
无向图：
1).欧拉路：
①图连通，可用并查集判定；
②度数为奇数的结点为2个。(一个作起点，一个作终点)
2）欧拉回路：
①图连通
②度数为奇数的结点为0个
有向图：
1）欧拉路：
①图连通。从某点开始能将所有访问 dfs+vis[]，见POJ2337
②起点的出度比入度大1，终点的入度比出度大1，其他结点的出度=入度
2）欧拉回路
②图连通
②所有结点的出度=入度
3.题目练习：
poj2337
思路:向前星先加入的边后访问
#include <iostream> #include <cstring> #include <string> #include <algorithm> #include <vector> #include <set> using namespace std; const int MAXN=1005; struct Edge{ int to; int next; int index; bool mark; }es[MAXN]; int head[MAXN]; int tot; void addedge(int u,int v,int index) { es[tot].to=v; es[tot].next=head[u]; es[tot].mark=false; es[tot].index=index; head[u]=tot++; } set<int> node; int n; vector<string> vec; int indeg[30]; int outdeg[30]; int ans[MAXN]; int cnt; void dfs(int u) { for(int i=head[u];i!=-1;i=es[i].next) { if(!es[i].mark) { es[i].mark=true; dfs(es[i].to); ans[cnt++]=es[i].index; } } } int main() { int T; cin>>T; while(T--) { node.clear(); vec.clear(); tot=0; cnt=0; memset(head,-1,sizeof(head)); memset(indeg,0,sizeof(indeg)); memset(outdeg,0,sizeof(outdeg)); cin>>n; for(int i=0;i<n;i++) { string s; cin>>s; vec.push_back(s); } sort(vec.begin(),vec.end()); int start=100; for(int i=vec.size()-1;i>=0;i--) { string s=vec[i]; int u=s[0]-'a'; int v=s[s.length()-1]-'a'; addedge(u,v,i); node.insert(u); node.insert(v); outdeg[u]++; indeg[v]++; start=min(start,u); } int c1=0,c2=0,c3=0; for(int i=0;i<30;i++) { if(indeg[i]==0&&outdeg[i]==0) continue; if(indeg[i]==outdeg[i]) c1++; else if(outdeg[i]-indeg[i]==1) { c2++; start=i; } else if(indeg[i]-outdeg[i]==1) c3++; } if(!(c1==node.size()-2&&c2==1&&c3==1)&&!(c1==node.size()&&c2==0&&c3==0)) { cout<<"***"<<endl; continue; } dfs(start); if(cnt!=n) { cout<<"***"<<endl; continue; } for(int i=cnt-1;i>=0;i--) { cout<<vec[ans[i]]; if(i>0) cout<<"."; } cout<<endl; } return 0; }
HDU3018
思路：求一幅图是几笔画的，答案是度为奇数的结点个数/2，注意孤立点不算，且图不连通。
#include <cstdio> #include <cstring> #include <vector> #include <set> using namespace std; const int MAXN=100005; int deg[MAXN]; int par[MAXN]; int n,m; set<int> roots; vector<int> nodes[MAXN]; void prep() { for(int i=0;i<MAXN;i++) { par[i]=i; } } int fnd(int x) { if(x==par[x]) return x; return par[x]=fnd(par[x]); } void unite(int x,int y) { int a=fnd(x); int b=fnd(y); par[a]=b; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<MAXN;i++) nodes[i].clear(); roots.clear(); prep(); memset(deg,0,sizeof(deg)); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); deg[u]++; deg[v]++; unite(u,v); } for(int i=1;i<=n;i++) { int root=fnd(i); nodes[root].push_back(i); roots.insert(root); } int res=0; for(set<int>::iterator it=roots.begin();it!=roots.end();it++) { if(nodes[*it].size()==1)//孤立点不算 continue; int s=0; for(int i=0;i<nodes[*it].size();i++) { int u=nodes[*it][i]; if(deg[u]%2==1) s++; } if(s==0) res+=1; else res+=(s/2); } printf("%d ",res); } return 0; }
POJ1386
思路:一笔画问题,并查集判连通
#include <cstdio> #include <cstring> using namespace std; int indeg[30]; int outdeg[30]; int vis[30]; int par[30]; void prep() { for(int i=0;i<30;i++) { par[i]=i; } } int fnd(int x) { if(x==par[x]) return x; return par[x]=fnd(par[x]); } void unite(int x,int y) { int a=fnd(x); int b=fnd(y); par[a]=b; } int main() { int T; scanf("%d",&T); while(T--) { memset(indeg,0,sizeof(indeg)); memset(outdeg,0,sizeof(outdeg)); memset(vis,0,sizeof(vis)); prep(); int n; scanf("%d",&n); int nodes=0; char word[1005]=""; for(int i=0;i<n;i++) { scanf("%s",word); int len=strlen(word); int u=word[0]-'a'; int v=word[len-1]-'a'; unite(u,v); if(!vis[u]) { vis[u]=1; nodes++; } if(!vis[v]) { vis[v]=1; nodes++; } outdeg[u]++; indeg[v]++; } int c1=0,c2=0,c3=0; for(int i=0;i<30;i++) { if(indeg[i]==0&&outdeg[i]==0) continue; if(outdeg[i]-indeg[i]==1) { c1++; } else if(outdeg[i]==indeg[i]) { c2++; } else if(indeg[i]-outdeg[i]==1) { c3++; } } if(!(c1==1&&c2==nodes-2&&c3==1)&&!(c1==0&&c2==nodes&&c3==0)) { printf("The door cannot be opened. "); continue; } int cnt=0; int root=-1; for(int i=0;i<30;i++) { if(vis[i]) { int f=fnd(i); if(f!=root) { root=f; cnt++; } } } if(cnt!=1) { printf("The door cannot be opened. "); } else { printf("Ordering is possible. "); } } return 0; }
POJ2513
思路：字典树+无向图一笔画问题
#include <cstdio> #include <cstring> using namespace std; const int MAXN=510005; struct Trie{ int val; Trie *next[26]; }; Trie memory[MAXN]; Trie *root; int tot; int deg[MAXN]; Trie* Create() { Trie *p=&memory[tot++]; for(int i=0;i<26;i++) p->next[i]=NULL; return p; } void Insert(char buf[],int x) { int len=strlen(buf); Trie *p=root; for(int i=0;i<len;i++) { int k=buf[i]-'a'; if(p->next[k]==NULL) { p->next[k]=Create(); } p=p->next[k]; } p->val=x; } int Search(char buf[]) { int len=strlen(buf); Trie *p=root; for(int i=0;i<len;i++) { int k=buf[i]-'a'; if(p->next[k]==NULL) { return -1; } p=p->next[k]; } return p->val; } int par[MAXN]; void prep() { for(int i=0;i<=MAXN;i++) { par[i]=i; } } int fnd(int x) { if(x==par[x]) return x; return par[x]=fnd(par[x]); } void unite(int x,int y) { int a=fnd(x); int b=fnd(y); par[a]=b; } int main() { root=Create(); int cnt=0; char first[15]=""; char last[15]=""; prep(); while(scanf("%s%s",first,last)!=EOF) { int x=Search(first); int y=Search(last); if(x==-1) { x=cnt; Insert(first,x); cnt++; } if(y==-1) { y=cnt; Insert(last,y); cnt++; } deg[x]++; deg[y]++; unite(x,y); } int odds=0; int rt=-1,roots=0; for(int i=0;i<cnt;i++) { int f=fnd(i); if(f!=rt) { rt=f; roots++; } if(deg[i]%2==1) odds++; } if(roots<=1&&(odds==0||odds==2)) { printf("Possible "); } else { printf("Impossible "); } return 0; }