您的位置: 首页  >  IT文章  >  欧拉回路 小结

欧拉回路 小结

分类: IT文章 • 2022-03-08 19:44:57

　　已经有人做过很好的总结了。可以参考 http://www.cnblogs.com/buptLizer/archive/2012/04/15/2450297.html

　　欧拉图的几种题型：

　　　　1、一笔画问题。（1）一个图需要几笔完成。（2）判断一个图是不是欧拉通路，有的严格要求是欧拉回路。（注：欧拉回路是起点和终点相同的欧拉通路）

　　　　2、输出欧拉路径。先判断是不是欧拉回路（欧拉通路），然后输出路径。

　　hdu1878　　

　　判断无向图是不是欧拉回路。条件是：1、图是连通的。2、图中没有奇数度的点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int d[N],r[N],f[N],vis[N];
int Find(int x)
{
    return x==f[x]?x:f[x]=Find(f[x]);
}
void Link(int x, int y)
{
    int a=Find(x),b=Find(y);
    if(a!=b)
    {
        f[b]=a; r[a]+=r[b];r[b]=0;
    }
}
void init()
{
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<N;i++)
        f[i]=i,r[i]=1;
}
int main()
{
    //freopen("test.txt","r",stdin);
    int n,m,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n) break;
        init();
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&i,&j);
            Link(i,j);
            vis[i]=1; vis[j]=1;
            d[i]++;d[j]++;
        }
        int s=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i]&&r[i]) s++;
        }
        if(s>1) {printf("0
"); continue;}
        for(i=1;i<=n;i++)
            if(d[i]%2==1) break;
        if(i<=n) printf("0
");
        else printf("1
");
    }
    return 0;
}
View Code

　　hdu3018

　　求一幅图最少需要几笔才能画完。（题目是这种类型的变形）

　　做法是：对每一个集合（等价类），如果是欧拉通路，就可以一笔画完；如果不是欧拉通路，就最少需要奇数度顶点的个数/2才能画完。

　　具体的实现是用一个STL里的vector数组记录属于该集合的点的下标。合并的时候，把小的数组里的元素放到大的数组里，小的清空。初始化的时候，先清空，再让i数组存i元素。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100010;
vector<int> st[N];
int d[N],r[N],f[N],vis[N];
int Find(int x)
{
    return x==f[x]?x:f[x]=Find(f[x]);
}
void Link(int x, int y)
{
    int a=Find(x),b=Find(y);
    if(a!=b)
    {
        if(r[a]>=r[b])
        {
            f[b]=a; r[a]+=r[b];r[b]=0;
            for(int i=0;i<st[b].size();i++)
                st[a].push_back(st[b][i]);
            st[b].clear();
        }
        else
        {
            f[a]=b; r[b]+=r[a];r[a]=0;
            for(int i=0;i<st[a].size();i++)
                st[b].push_back(st[a][i]);
            st[a].clear();
        }
    }
}
void init(int n)
{
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        f[i]=i,r[i]=1;
        st[i].clear();
        st[i].push_back(i);
    }
}
int main()
{
    //freopen("test.txt","r",stdin);
    int n,m,i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(n);
        while(m--)
        {
            scanf("%d%d",&i,&j);
            Link(i,j);
            vis[i]=1; vis[j]=1;
            d[i]++;d[j]++;
        }
        int s=0;
        k=0;
        for(i=1;i<=n;i++)
        {
            s=0;
            if(vis[i]&&r[i])
            {
                for(j=0;j<st[i].size();j++)
                    if(d[st[i][j]]%2) s++;
                if(s==0) k++;
                else k+=s/2;
            }
        }
        printf("%d
",k);
    }
    return 0;
}
View Code

　　hdu1116/poj1386 　　有向图的欧拉通路的判断。

　　单词接龙，第二个单词的第一个字母只要和第一个单词的最后一个字母相同，就可以连起来。问可不可以接成一条龙。

　　要注意的是，如果一个单词的首尾是一样的，不能忽略。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=30;
int od[N],id[N],r[N],f[N],vis[N];
int Find(int x)
{
    return x==f[x]?x:f[x]=Find(f[x]);
}
void Link(int x, int y)
{
    int a=Find(x),b=Find(y);
    if(a!=b)
    {
        f[b]=a; r[a]+=r[b];r[b]=0;
    }
}
void init()
{
    memset(id,0,sizeof(id));
    memset(od,0,sizeof(od));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<N;i++)
        f[i]=i,r[i]=1;
}
int main()
{
    //freopen("test.txt","r",stdin);
    int cas,i,j,k,m,n;
    char str[1010];
    scanf("%d",&cas);
    while(cas--)
    {
        init();
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",str);
            n=strlen(str);
            i=str[0]-96; j=str[n-1]-96;
            Link(i,j);
            vis[i]=1; vis[j]=1;
            od[i]++;id[j]++;
        }
        int s=0;
        n=26;
        for(i=1;i<=n;i++)
        {
            if(vis[i]&&r[i]) s++;
        }
        if(s>1) {printf("The door cannot be opened.
"); continue;}
        int a=0,b=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i]&&id[i]!=od[i])
            {
                if(od[i]-id[i]==1) a++;
                else if(od[i]-id[i]==-1) b++;
                else break;
            }
        }
        if(i<=n)printf("The door cannot be opened.
");
        else if((a==1&&b==1)||(a+b==0)) printf("Ordering is possible.
");
        else printf("The door cannot be opened.
");
    }
    return 0;
}
View Code

　　poj2230    输出欧拉路径（依次输出点）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100010,N=10010;
struct node
{
    int to,next;
}e[maxn];
int p[N],vis[maxn];
void euler(int x)
{
    int i;
    for(i=p[x];i!=-1;i=e[i].next)
        if(!vis[i])
        {
            vis[i]=1;
            euler(e[i].to);
        }
    printf("%d
",x);
}
int main()
{
    //freopen("test.txt","r",stdin);
    int n,m,i,j,k,x,y;
    memset(vis,0,sizeof(vis));
    memset(p,-1,sizeof(p));
    scanf("%d%d",&n,&m);
    k=0;
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        e[k].to=y;
        e[k].next=p[x];
        p[x]=k++;
        e[k].to=x;
        e[k].next=p[y];
        p[y]=k++;
    }
    euler(1);
    return 0;
}
View Code

　　poj2337

　　题意与poj1386相同，不过需要要求输出字典序最小的路径。字典序最小什么的，真让人讨厌。

　　可以参照克鲁斯卡尔算法算最小生成树时，怎么输出字典序最小。（边排序的时候，起点和终点都要考虑）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N =26,M=1010;
char ret[M][N];
int anc[N],id[N],od[N],f[N];
bool vis[M],w[N];
//边的标记、字母的标记
int r,t;
struct node
{
    int to,next;
    char str[22];
}e[M];
bool cmp (node a,node b)
{
    return strcmp(a.str,b.str)>0;
}
int Find(int x)
{
    if(anc[x]>=0)
    {
        anc[x]=Find(anc[x]);
        return anc[x];
    }
    return x;
}
void Union(int x,int y)
{
    int r1=Find(x);
    int r2=Find(y);
    if(r1==r2) return ;
    int n1=anc[r1];
    int n2=anc[r2];
    if(n1<n2) {anc[r1]=r2;anc[r2]+=n1;}
    else {anc[r2]=r1;anc[r1]+=n2;}
}
void euler(int a,int b)
{
    int i;
    for(i=f[a];i!=-1;i=e[i].next)
    {
        if(!vis[i])
        {
            vis[i]=1;
            euler(e[i].to,i);
        }
    }
    if(b>=0) strcpy (ret[r++],e[b].str);
}
int main()
{
    //freopen("test.txt","r",stdin);
    int ca,m,i,j,k,n,x,y;
    scanf("%d",&ca);
    while(ca--)
    {
        memset(anc,-1,sizeof(anc));
        memset(vis,0,sizeof(vis));
        memset(f,-1,sizeof(f));
        for(i=0;i<N;i++) w[i]=id[i]=od[i]=0;
        scanf("%d",&m);
        if(!m) continue;
        getchar();
        for(i=0;i<m;i++) gets(e[i].str);
        sort(e,e+m,cmp);
        t=0;
        for(i=0;i<m;i++)
        {
            n=strlen(e[i].str);
            x=e[i].str[0]-97;
            y=e[i].str[n-1]-97;
            id[y]++;
            od[x]++;
            w[x]=1;
            w[y]=1;
            Union(x,y);
            e[t].to=y;
            e[t].next=f[x];
            f[x]=t++;
        }
        int scc=0;
        //连通分支数
        for(i=0;i<N;i++)
        {
            if(w[i]&&anc[i]<0) scc++;
            if(scc>1) break;
        }

        if(scc>1)
        {
            printf("***
");
            continue;
        }
        x=y=0;
        k=-1;//起点
        for(i=0;i<N;i++)
        {
            if(w[i]&&id[i]!=od[i])
            {
                if((id[i]-od[i])==1) x++;
                else if((od[i]-id[i])==1) {y++;k=i;}
                else break;
            }
        }

        if(i<N) printf("***
");
        else
        {
            if(!((x+y==0)||(x==1&&y==1))) {printf("***
");continue;}
            if(k==-1)
            {
                for(i=0;i<N;i++)
                    if(od[i]) break;
                k=i;
            }
            r=0;
            euler(k,-1);
            printf("%s",ret[r-1]);
            for(i=r-2;i>=0;i--) printf(".%s",ret[i]);
            printf("
");
        }
    }
    return 0;
}
View Code

　　

　　

　　

　　

相关推荐