精华内容
下载资源
问答
  • 题目大意:欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到...解题思路:判断无向图是否存在欧拉回路判断每个点的度数是否为偶数+并查集确认连通性。 代码: 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;
    }
    展开全文
  • 判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法: 一、无向图 每个顶点的度数都是偶数,则存在欧拉回路。 二、有向图(所有边都是单向的) 每个...
    判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法:
    一、无向图
    每个顶点的度数都是偶数,则存在欧拉回路。
    二、有向图(所有边都是单向的)
    每个节顶点的入度都等于出度,则存在欧拉回路。
    以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。
    三、混合图(有的边是单向的,有的边是无向的。常被用于比喻城市里的交通网络,有的路是单行道,有的路是双行道。)
    找到一个给每条无向的边定向的策略,使得每个顶点的入度等于出度,这样就能转换成上面第二种情况。这就可以转化成一个二部图最大匹配问题。网络模型如下:


    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 &...

    欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?
    Input
    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结
    束。
    Output
    每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。
    Sample Input
    3 3
    1 2
    1 3
    2 3
    3 2
    1 2
    2 3
    0
    Sample Output
    1
    0在这里插入图片描述

    #include<stdio.h>
    #include<string.h>
    int a[1001],n,m;
    int b[1001];
    int par[1001];
    int find(int root)
    {
        if(root!=par[root])
            par[root]=find(par[root]);
        return par[root];
    }
    int main()
    {
        while(~scanf("%d",&n)&&n!=0)
        {
            memset(a,0,sizeof(a));
            int i,t=0,flog=0,t1,t2,r1,r2;
            for(i=1; i<n; i++)
                par[i]=i;
            scanf("%d",&m);
            for(i=0; i<m; i++)
            {
                scanf("%d %d",&t1,&t2);
                if(par[t1]!=par[t2])
                {
                    r1=find(par[t1]);
                    r2=find(par[t2]);
                    par[r1]=r2;
                }
                a[t1]++;
                a[t2]++;
            }
            for(i=1; i<=n; i++)
            {
                if(find(i)!=find(1))
                {
                    flog=0;
                    break;
                }
                if(a[i]%2==0)
                    flog++;
            }
            if(flog==n)
                flog=1;
            else
                flog=0;
            printf("%d\n",flog);
        }
    }
    

    Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

    There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm'' can be followed by the wordmotorola’’. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
    Input
    The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters ‘a’ through ‘z’ will appear in the word. The same word may appear several times in the list.
    Output
    Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
    If there exists such an ordering of plates, your program should print the sentence “Ordering is possible.”. Otherwise, output the sentence “The door cannot be opened.”.
    Sample Input
    3
    2
    acm
    ibm
    3
    acm
    malform
    mouse
    2
    ok
    ok
    Sample Output
    The door cannot be opened.
    Ordering is possible.
    The door cannot be opened.

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    char s[100101];
    int in[30],out[30];
    int par[100];
    int find(int root)
    {
        if(par[root]!=root)
            par[root]=find(par[root]);
        return par[root];
    }
    int main()
    {
        int p;
        scanf("%d",&p);
        int i,j;
        while(p--)
        {
            for(i=1; i<=30; i++)
                par[i]=i;
            int n,ans=0,sum1=0,sum2=0;
            scanf("%d",&n);
            memset(in,0,sizeof(in));
            memset(out,0,sizeof(out));
            while(n--)
            {
                scanf("%s",s);
                int t=strlen(s);
                int a=s[0]-'a'+1;
                int b=s[t-1]-'a'+1;
                in[a]++;
                out[b]++;
                par[find(a)]=find(b);
            }
            for(i=1; i<=26; i++)
                if((out[i])&&find(i)==i||abs(in[i]-out[i])>1)
                //判断点是否是起点且在图中 //出度与入度最大差值不能超过1
                    ans++;
            if(ans>1)
            {
                printf("The door cannot be opened.\n");
                continue;
            }
            for(i=1; i<=26; i++)
            {
                if(in[i]>out[i])
                    sum1++;
                if(in[i]<out[i])
                    sum2++;
            }
            //要么是欧拉路起点和终点度相差为1 //或者是欧拉回路所有的的出度与入度都一样
            if(sum1==1&&sum2==1||sum1==0&&sum2==0)
                printf("Ordering is possible.\n");
            else
                printf("The door cannot be opened.\n");
        }
    }
    
    
    展开全文
  • 原文地址:判断欧拉回路是否存在的方法作者:万剑山河 判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法: 一、无向图 每个顶点的度数都是偶数,则...
  • // POJ 2337 欧拉路径 // // Created by 郑喆君 on 8/7/14. // Copyright (c) 2014 itcast. All rights reserved. // #include #include #include #include #include #include #include #include #incl
  • 存在欧拉回路的条件:所有顶点的度为偶数,并且图是联通的(每个点都可以遍历) 代码: #include #include #include #include #include #include #include #include #include #include #include using namespace ...
  • 无向图判断欧拉回路

    2018-07-06 19:20:45
    // // oula.cpp // 666 // // Created by Terry on 2018/7/6. ...// 如果无向图连通并且所有结点的度都是偶数,则存在欧拉回路,否则不存在。  #include &lt;iostream&gt; #include &lt;cstring&...
  • 7-12 哥尼斯堡的“七桥问题” (25 分) 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿...这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以...
  • 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 欧拉回路是指不令笔离开纸面,可画...
  • POJ 1300 判断欧拉回路

    2013-06-14 19:47:42
    题意:能否找到一条路径经过所有开着门的房间,并使得:1:通过门后立即把门关上,2:关上的门不在...本题实际上是判断一个图中是否存在欧拉回路或者欧拉通路。 无向图存在欧拉回路的充要条件 一个无向图存在欧拉回
  • (有任何问题欢迎留言或私聊 ... 判断途中是否存在欧拉回路(一条路径不重复地经过所有的边一次)。 思路:  1. 不论无向边的方向怎么指定,若存在欧拉回路,每个点出度和入度的差一定为偶数。因为有...
  • 其实一笔画问题又叫欧拉回路,是指在画的过程中,笔不离开纸,且图中每条边仅画一次,而且可以回到起点的一条回路。 蒜头君打算考考你,给你一个图,问是否存在欧拉回路? 输入格式 第11行输入两个正整数,分别是...
  • 欧拉回路: 两种情况 所有点度为偶数,且出发点一定是终止点 有两个奇数度点,分别为出发点和终止点 // ShellDawn // POJ1300 // No.17 #include<cstdio> #include<iostream> #include&...
  • 解题思路: 想多了····还看了Fleury算法·····又想用并查集、dfs判断...无向图欧拉回路判断:每个顶点的度数都是偶数,就存在欧拉回路。 暴力O(n^2) 完整代码: #include #include #include
  • POJ 1386 判断欧拉回路

    2016-07-12 19:36:21
    题意:要开启一扇门,n个单词是密码,n个单词中,如果一个单词的首字母和前一个单词的尾字母相同,并且每个单词都能这么连起来且只用一次,则门可以开启,否则不能开启,现给出单词,判断门是否可以开。有向图欧拉...
  • 思路:就是求欧拉回路的问题,不过建图应该是无向图。所以是求无向图的欧拉回路。因为数据给的少,所以直接邻接矩阵即可。 /** * 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:
  • poj1300判断欧拉回路

    2014-07-17 13:57:00
    对于连通图 无向图:1.无奇点,可以从任意一点出发回到原点。 2.存在奇点,且只有两个,从一奇点出发,另一奇点终止。 有向图:1.所有点入度等于出度。 2.只有两个点入度不等于出度,且其中一个点入度比出度......
  • 题意: 给你N个房间(图节点)以及房间之间的门(图的边),且给你初始的房间号M,问你从初始房间走,可不可以经过每个门仅1次,最后到达0号房间.且所有的门都被你走过1次? #include <cstdio> #include <...

空空如也

空空如也

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

判断欧拉回路