精华内容
下载资源
问答
  • 题目大意:欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到...解题思路:判断无向图是否存在欧拉回路判断每个点的度数是否为偶数+并查集确认连通性。 代码: 1 #include<iostream> ...

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1878

    题目大意:欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?

    解题思路:判断无向图是否存在欧拉回路,判断每个点的度数是否为偶数+并查集确认连通性。

    代码:

     1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #define CLR(arr,val) memset(arr,val,sizeof(arr))
     5 using namespace std;
     6 const int N=1e3+5;
     7 
     8 int n,m;
     9 int root[N],indeg[N],outdeg[N];
    10 
    11 int find(int x){
    12     return root[x]==x?x:root[x]=find(root[x]);
    13 }
    14 
    15 int main(){
    16     while(scanf("%d",&n)!=EOF){
    17         if(n==0)
    18             break;        
    19         CLR(indeg,0);
    20         CLR(outdeg,0);
    21         for(int i=1;i<=n;i++)
    22             root[i]=i;
    23         scanf("%d",&m);
    24         int a,b,x,y;
    25         for(int i=1;i<=m;i++){
    26             scanf("%d%d",&a,&b);
    27             indeg[b]++;
    28             outdeg[a]++;
    29             x=find(a),y=find(b);
    30             if(x!=y)
    31                 root[x]=y;
    32         }
    33         bool flag=true;
    34         int cnt=0;
    35         for(int i=1;i<=n;i++){
    36             if(find(i)==i)
    37                 cnt++;
    38             if((indeg[i]+outdeg[i])%2!=0){
    39                 flag=false;
    40                 break;
    41             }
    42         }
    43         if(flag&&cnt==1)
    44             puts("1");
    45         else
    46             puts("0");
    47     }
    48     return 0;
    49 }

     

    转载于:https://www.cnblogs.com/fu3638/p/7922931.html

    展开全文
  • 主要是好像下一道题就是求 欧拉回路的。。 用dfs判断连通性,或者用并查集都行。 还是研究生复试题,好水。。 看来我考研有希望了qwq 欧拉回路的条件。(就是一笔画问题啦) ① 无向图 一个连通块,所有顶点...

    http://acm.hdu.edu.cn/showproblem.php?pid=1878
    主要是好像下一道题就是求 欧拉回路的。。
    用dfs判断连通性,或者用并查集都行。
    还是研究生复试题,好水。。
    看来我考研有希望了qwq
    欧拉回路的条件。(就是一笔画问题啦)
    ① 无向图
    一个连通块,所有顶点度数均为偶数。
    ② 有向图
    所有顶点入度等于出度
    欧拉通路(就是画完,并不是回路,但是要画完)
    无向图
    ① 奇度顶点个数为0或者2个。
    有向图
    ② 所有入度等于出度,或者只有两个不等于,一个入度大于出度1,一个入度小出度一个
    混合图欧拉回路(不会,就像不会双调旅行商那样。。)

     #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e3+3;
    int du[1004];
    int fa[1004];
    void init(){
       for(int i=0;i<1004;i++)
           fa[i]=i;
    }
    int  find1(int a){
        if(a==fa[a]) return a;
        return fa[a]=find1(fa[a]);
    }
    void unite(int a,int b){
        int x=find1(a);
        int y=find1(b);
        if(x!=y)
            fa[a]=y;
        return ;
    }
    int main()
    {    int m,n,a,b;
         while(~scanf("%d",&m)){
              if(m==0)break;
              scanf("%d",&n);
              memset(du,0,sizeof(du));
              init();
              for(int i=0;i<n;i++){
                  scanf("%d%d",&a,&b);
                 unite(a,b);
                 du[a]++;du[b]++;
              }
              bool flag=true;
              int sum=0;
              for(int i=1;i<=m;i++){
                  if(fa[i]==i)
                    sum++;
              }
              if(sum>1) flag=false;
              for(int i=1;i<=m;i++){
                  if(du[i]&1)
                    flag=false;
              }
              if(flag)
                puts("1");
              else
                puts("0");
         }
        return 0;
    }
    
    
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e3+3;
    vector<int>G[maxn];
    bool vis[maxn];
    int du[maxn];
    void dfs(int u){
         vis[u]=true;
         for(int i=0;i<G[u].size();i++){
            int to=G[u][i];
            if(!vis[to]){
                dfs(to);
            }
         }
    }
    int main()
    {    int m,n,a,b;
         while(~scanf("%d",&m)){
              if(m==0)break;
              scanf("%d",&n);
              for(int i=0;i<maxn;i++)
                  G[i].clear();
              memset(vis,false,sizeof(vis));
              memset(du,0,sizeof(du));
              for(int i=0;i<n;i++){
                  scanf("%d%d",&a,&b);
                 G[a].push_back(b);
                 G[b].push_back(a);
                 du[a]++;du[b]++;
              }
              bool flag=true;
              dfs(1);
              for(int i=1;i<=m;i++){
                  if(!vis[i]) flag=false;
              }
              for(int i=1;i<=m;i++){
                  if(du[i]&1)
                    flag=false;
              }
              if(flag)
                puts("1");
              else
                puts("0");
         }
        return 0;
    }
    展开全文
  • 如何判断欧拉回路

    2021-06-22 20:13:14
    以下判断基于此图的基图连通。 无向图存在欧拉回路的充要条件 一个无向图存在欧拉回路,当且仅当该图所有顶点...那么如果存在一个图G’使得G’存在欧拉回路,那么G就存在欧拉回路。 其思路就将混合图转换成有向图判断

    以下判断基于此图的基图连通。
    无向图存在欧拉回路的充要条件
    一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图。
    有向图存在欧拉回路的充要条件
    一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图。
    混合图存在欧拉回路条件
    要判断一个混合图G(V,E)(既有有向边又有无向边)是欧拉图,方法如下:
    假设有一张图有向图G’,在不论方向的情况下它与G同构。并且G’包含了G的所有有向边。那么如果存在一个图G’使得G’存在欧拉回路,那么G就存在欧拉回路。
    其思路就将混合图转换成有向图判断。实现的时候,我们使用网络流的模型。现任意构造一个G’。用Ii表示第i个点的入度,Oi表示第i个点的出度。如果存在一个点k,|Ok-Ik|mod 2=1,那么G不存在欧拉回路。接下来则对于所有Ii>Oi的点从源点连到i一条容量为(Ii-Oi)/2的边,对于所有Ii<Oi的点从i连到汇点一条容量为(Oi-Ii)/2的边。如果对于节点U和V,无向边(U,V)∈E,那么U和V之间互相建立容量为1的边。如果此网络的最大流等于∑|Ii-Oi|/2,那么就存在欧拉回路。

    展开全文
  • 判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法: 一、无向图 每个顶点的度数都是偶数,则存在欧拉回路。 二、有向图(所有边都是单向的) 每个...
    判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法:
    
    一、无向图
    每个顶点的度数都是偶数,则存在欧拉回路。
    二、有向图(所有边都是单向的)
    每个节顶点的入度都等于出度,则存在欧拉回路。
    以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。
    三、混合图(有的边是单向的,有的边是无向的。常被用于比喻城市里的交通网络,有的路是单行道,有的路是双行道。)
    找到一个给每条无向的边定向的策略,使得每个顶点的入度等于出度,这样就能转换成上面第二种情况。这就可以转化成一个二部图最大匹配问题。网络模型如下:


    1. 新建一个图。
    2. 对于原图中每一条无向边i,在新图中建一个顶点e(i);
    3. 对于原图中每一个顶点j,在新图中建一个顶点v(j)。
    4. 如果在原图中,顶点j和k之间有一条无向边i,那么在新图中从e(i)出发,添加两条边,分别连向v(j)和v(k),容量都是1。
    5. 在新图中,从源点向所有e(i)都连一条容量为1的边。
    6. 对于原图中每一个顶点j,它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度,从而使它的入度等于总度数的一半,也就是(in + out + un) / 2(显然与此同时出度也是总度数的一半,如果总度数是偶数的话)。当然,如果in已经大于总度数的一半,或者总度数是奇数,那么欧拉回路肯定不存大。如果in小于总度数的一半,并且总度数是偶数,那么我们在新图中从v(j)到汇点连一条边,容量就是(in + out + un) / 2 – in,也就是原图中顶点j还需要多少入度。

    按照这个网络模型算出一个最大流,如果每条从v(j)到汇点的边都达到满流量的话,那么欧拉回路成立。



    思路:并查集,然后判断所有点的度数以及图是否连通


    #include <limits.h>
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    #include <algorithm>
    #include <iostream>
    #include <iterator>
    #include <sstream>
    #include <queue>
    #include <stack>
    #include <string>
    #include <vector>
    #include <set>
    #include <map>
    //#define ONLINE_JUDGE
    #define eps 1e-6
    #define INF 0x7fffffff                                          //INT_MAX
    #define inf 0x3f3f3f3f                                          //int??????????????????
    #define FOR(i,a) for((i)=0;i<(a);(i)++)                          //[i,a);
    #define MEM(a) (memset((a),0,sizeof(a)))
    #define sfs(a) scanf("%s",a)
    #define sf(a) scanf("%d",&a)
    #define sfI(a) scanf("%I64d",&a)
    #define pf(a) printf("%d\n",a)
    #define pfI(a) printf("%I64d\n",a)
    #define pfs(a) printf("%s\n",a)
    #define sfd(a,b) scanf("%d%d",&a,&b)
    #define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
    #define for1(i,a,b) for(int i=(a);i<b;i++)
    #define for2(i,a,b) for(int i=(a);i<=b;i++)
    #define for3(i,a,b)for(int i=(b);i>=a;i--)
    #define MEM1(a) memset(a,0,sizeof(a))
    #define MEM2(a) memset(a,-1,sizeof(a))
    #define MEM3(a) memset(a,0x3f,sizeof(a))
    #define MEMS(a) memset(a,'\0',sizeof(a))
    #define LL __int64
    const double PI = acos(-1.0);
    template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
    template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
    template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
    template<class T> inline T Max(T a, T b) { return a > b ? a : b; }
    using namespace std;
    template<class T>
    T Mint(T a, T b, T c) {
        if (a>b) {
            if (c>b)
                return b;
            return c;
        }
        if (c>a)
            return a;
        return c;
    }
    template<class T>
    T Maxt(T a, T b, T c) {
        if (a>b) {
            if (c>a)
                return c;
            return a;
        }
        else if (c > b)
            return c;
        return b;
    }
    
    const int maxn=1005;
    int T,n,m;
    int f[maxn],d[maxn];
    int a,b;
    
    void Make_Set(int x){
    	f[x]=x;
    }
    
    int find(int x){
    	return x==f[x]?x:find(f[x]);
    }
    
    void Union(int a,int b){
    	a=find(a);
    	b=find(b);
    	if(a==b) return ;
    	if(a<=b) f[b]=a;
    	else f[a]=b;
    }
    
    int main(){
    #ifndef ONLINE_JUDGE
    	freopen("test.in","r",stdin);
    	freopen("test.out","w",stdout);
    #endif
    	while(~sf(n)&&n){
    		sf(m);
    		MEM1(d);
    		for2(i,1,n)
    			Make_Set(i);
    		while(m--){
    			sfd(a,b);
    			d[a]++;d[b]++;
    			Union(a,b);
    		}
    		int ans=0,num=0;
    		for2(i,1,n){
    			ans++;
    			if(d[i]%2) break;
    			if(find(i)==i) num++;
    		}
    		if(ans==n&&num==1) puts("1");
    		else puts("0");
    	}
    	return 0;
    }
    


    展开全文
  • 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Input 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 &...
  • 原文地址:判断欧拉回路是否存在的方法作者:万剑山河 判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法: 一、无向图 每个顶点的度数都是偶数,则...
  • 存在欧拉回路的条件:所有顶点的度为偶数,并且图是联通的(每个点都可以遍历) 代码: #include #include #include #include #include #include #include #include #include #include #include using namespace ...
  • // POJ 2337 欧拉路径 // // Created by 郑喆君 on 8/7/14. // Copyright (c) 2014 itcast. All rights reserved. // #include #include #include #include #include #include #include #include #incl
  • 解题思路: 想多了····还看了Fleury算法·····又想用并查集、dfs判断...无向图欧拉回路判断:每个顶点的度数都是偶数,就存在欧拉回路。 暴力O(n^2) 完整代码: #include #include #include
  • 无向图判断欧拉回路

    2018-07-06 19:20:45
    // // oula.cpp // 666 // // Created by Terry on 2018/7/6. ...// 如果无向图连通并且所有结点的度都是偶数,则存在欧拉回路,否则不存在。  #include &lt;iostream&gt; #include &lt;cstring&...
  • hdu1878判断欧拉回路

    2013-08-14 15:14:00
    欧拉回路 Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8186Accepted Submission(s): 2926 Problem Description 欧拉回路是指不令笔离开纸面,可画...
  • 7-12 哥尼斯堡的“七桥问题” (25 分) 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿...这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以...
  • (有任何问题欢迎留言或私聊 ... 判断途中是否存在欧拉回路(一条路径不重复地经过所有的边一次)。 思路:  1. 不论无向边的方向怎么指定,若存在欧拉回路,每个点出度和入度的差一定为偶数。因为有...
  • POJ 1300 判断欧拉回路

    2013-06-14 19:47:42
    题意:能否找到一条路径经过所有开着门的房间,并使得:1:通过门后立即把门关上,2:关上的门不在...本题实际上是判断一个图中是否存在欧拉回路或者欧拉通路。 无向图存在欧拉回路的充要条件 一个无向图存在欧拉回
  • 欧拉回路: 两种情况 所有点度为偶数,且出发点一定是终止点 有两个奇数度点,分别为出发点和终止点 // ShellDawn // POJ1300 // No.17 #include<cstdio> #include<iostream> #include&...
  • POJ 1386 判断欧拉回路

    2016-07-12 19:36:21
    题意:要开启一扇门,n个单词是密码,n个单词中,如果一个单词的首字母和前一个单词的尾字母相同,并且每个单词都能这么连起来且只用一次,则门可以开启,否则不能开启,现给出单词,判断门是否可以开。有向图欧拉...
  • 其实一笔画问题又叫欧拉回路,是指在画的过程中,笔不离开纸,且图中每条边仅画一次,而且可以回到起点的一条回路。 蒜头君打算考考你,给你一个图,问是否存在欧拉回路? 输入格式 第11行输入两个正整数,分别是...
  • 思路:就是求欧拉回路的问题,不过建图应该是无向图。所以是求无向图的欧拉回路。因为数据给的少,所以直接邻接矩阵即可。 /** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date...
  • POJ 1003 判断欧拉回路

    千次阅读 2012-08-07 16:13:06
    题意:有N个房间,每个房间都有若干门通往...思路:因为各个房间一定是连通的,所以判断是否能够一圈走完所有的路,则以房间为点,门为边的图必定是欧拉回路(有限图G是一条道路(即可以一笔画成)的充分必要条件是G
  • 题目大意:给一个图,有的边有向,有的边无向,问能否找到一条回路恰好经过每条边一次。 解题思路: 模型近似于欧拉回路了,但是边的性质不唯一。...这样来看,有向图和无向图的欧拉回路判断的本质就统一了
  • /********************** * author:crazy_石头 * Pro:HDU1878 ...* 无向图判欧拉回路:若能dfs整个图即图是联通的还有每个顶点度数为偶数即可形成欧拉回路 * Judge Status:Accepted * Memory:4184K * Time:
  • 并查集求欧拉回路和通路 Sample Input 3 2 acm ibm 3 acm malform mouse 2 ok okSample Output The door cannot be opened. Ordering is possible. The door cannot be opened. 1 #includ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,434
精华内容 2,173
关键字:

判断欧拉回路