bg游戏资讯:一笔画问题,图的连通性

作者: 单机闯关小游戏  发布:2019-08-30

描述

bg游戏资讯:一笔画问题,图的连通性。一笔画难题

bg游戏资讯:一笔画问题,图的连通性。时限:2000 ms  |  内存限制:65535 KB

bg游戏资讯:一笔画问题,图的连通性。难度:4

 

描述
zyc从小就相比欣赏玩一些小游戏,当中就总结画一笔画,他想请你帮她写贰个顺序,判定二个图是否可以用一笔画下去。

规定,全体的边都只好画一遍,不可能再一次画。

 

 

输入
首先行唯有贰个正整数N(N<=10)表示测验数据的组数。
每组测验数据的率先行有八个正整数P,Q(P<=一千,Q<=两千),分别代表那些画中有多少个终端和多少条连线。(点的号码从1到P)
随着的Q行,每行有多少个正整数A,B(0<A,B<P),表示编号为A和B的两点时期有连线。

输出
即使存在符合条件的连线,则输出"Yes",
假定不设有符合条件的连线,输出"No"。

样例输入
2 4 3 1 2 1 3 1 4 4 5 1 2 2 3 1 3 1 4 3 4

样例输出
No Yes

大旨来自:

bg游戏资讯:一笔画问题,图的连通性。标题深入分析:

bg游戏资讯:一笔画问题,图的连通性。bg游戏资讯:一笔画问题,图的连通性。欧拉定理   借使一个网络是连接的还要奇顶点的个数等于0或2,那么它能够一笔画出;不然它不得以一笔画出。

认清一笔画的不二秘籍:

  ①是连着的。一个图,假若图上Infiniti制二点总无线条连接着,就称为连通的。不是连接的就不可能一笔画出。

  ②奇点个数是0恐怕是2。图上线段的端点能够分为二类,奇点和偶数。三个点,以它为端点的线条数是奇数就叫做奇点,线段数是偶数就称为偶点。

  四个图是或不是是一笔画就看奇点的个数,奇点个数是 0 恐怕2,正是一笔画,不然就不是一笔画。

之所以那些主题材料完全可以转账计策为:

           第一步: 首先大家不管它三七二十几,先进行连通性的论断。

           第二步:

                      (1)假设是对接的,我们来判断此图的度的奇点的个数是0大概是2 ,假如是,则表达那么些是欧拉图,即能够一笔画出,反之则不可能一笔画出

                      (2)假如是非连通的,那表明那么些图很定不可能一笔画出。

 

代码一:——深搜

 

 1 #include <stdio.h>
 2 #include <string.h>
 3 int P,Q;
 4 int bian[1005];
 5 bool map[1005][1005],vis[1005];
 6 void dfs(int cur)
 7 {
 8     vis[cur]=true;
 9     for(int i=1;i<=P;i  )
10         if(map[cur][i])
11         {
12             bian[cur]  ;
13             if(!vis[i])
14                 dfs(i);
15         }
16 }
17 
18 int main()
19 {
20     int T;
21     scanf("%d",&T);
22     while(T--)
23     {
24         int ok=1;
25         memset(map,false,sizeof(map));
26         memset(vis,false,sizeof(vis));
27         memset(bian,0,sizeof(bian));
28         
29         scanf("%d%d",&P,&Q);
30 
31         for(int i=0;i<Q;i  )
32         {
33             int A,B;
34             scanf("%d%d",&A,&B);
35             map[A][B]=true,map[B][A]=true;
36         }
37 
38         dfs(1);   // 判断是否连通的,如果vis有个false,就不是连通的
39         
40         for(int i=1;i<=P;i  )
41             if(!vis[i])
42             {
43                 ok=0;
44                 break;
45             }
46         
47         if(!ok)printf("Non");
48         else
49         {
50             int xx=0;
51             for(int i=1;i<=P;i  )
52                 if(bian[i]%2)xx  ;
53             if(xx==0||xx==2)printf("Yesn");
54             else printf("Non");
55         }
56     }
57     return 0;
58 }

 

在AC后,英特网看到人家的思绪,还恐怕有一种办法来决断连通性——并查集。

并查融资料:

代码二:——并查集

 

 1 //并查
 2 #include<stdio.h>
 3 #include<string.h>
 4 int father[1010],ans[1010];
 5 void init()
 6 {
 7     for(int i=0;i<1010;i  )
 8           father[i]=i;
 9 }
10 int find(int x)
11 {
12     if(father[x]==x)
13           return x;
14      else
15           return father[x]=find(father[x]);
16 }
17 int main()
18 {
19      int ncases,n,m,x,y,count,jdcount;
20      scanf("%d",&ncases);
21      while(ncases--)
22      {
23           memset(ans,0,sizeof(ans));
24           init();
25           count=jdcount=0;
26           scanf("%d %d",&n,&m);
27           for(int i=1;i<=m;i  )
28           {
29                scanf("%d %d",&x,&y);
30              ans[x]  ;   ans[y]  ;
31                x=find(x);  y=find(y);
32                if(x!=y)
33                 father[x]=father[y];
34           }
35           
36           for(i=1;i<=n;i  )
37            if(find(i)==i)
38             count  ;
39           for(i=1;i<=n;i  )
40               if(ans[i]%2==1)
41                   jdcount  ;
42           if((jdcount==0||jdcount==2)&&count==1)
43               printf("Yesn");
44           else
45               printf("Non");
46      }
47 } 

 

一笔画难题

日子范围:三千 ms  |  内部存款和储蓄器限制:65535 KB

难度:4

 

描述
zyc从小就相比喜欢玩一些小游戏,在那之中就回顾画一笔画,他想请您帮她写多少个前后相继,判别三个图是或不是能够用一笔画下来。

规定,全体的边都只可以画贰遍,不可能重新画。

 

 

输入
率先行独有二个正整数N(N<=10)表示测量试验数据的组数。
每组测量试验数据的第一行有三个正整数P,Q(P<=1000,Q<=三千),分别表示那么些画中有稍许个极点和不怎么条连线。(点的号子从1到P)
继之的Q行,每行有五个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。

输出
只要存在符合条件的连线,则输出"Yes",
若是荒诞不经符合条件的连线,输出"No"。

样例输入
2 4 3 1 2 1 3 1 4 4 5 1 2 2 3 1 3 1 4 3 4

样例输出
No Yes

来源
[张云聪]原创

欧拉回路

屠龙宝刀点击就送

#include <cstring>
#include <cstdio>
#include <queue>
#define Max 1500

using namespace std;

int du[Max],tx[Max][Max];
bool vis[Max];
bool flag;
int tot,N;
void dfs(int k,int M)
{
    vis[k]=1;
    for(int i=1;i<=M;  i)
    {
        if(tx[k][i])
        {
            du[i]  ;
            if(!vis[i])
            dfs(i,M);
        }
    }
}
int main()
{
    scanf("%d",&N);
    for(int p,q;N--;)
    {
        memset(du,0,sizeof(du));
        memset(tx,0,sizeof(tx));
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&p,&q);
        for(int x,y;q--;)
        {
            scanf("%d%d",&x,&y);
            tx[x][y]=tx[y][x]=1;
        }
        bool flag=true;
        dfs(1,p);
        for(int i=1;i<=p;  i)
        {
            if(!vis[i])
            flag=false;
        }
        if(!flag) printf("Non");
        else
        {
            int tot=0;
            for(int i=1;i<=p;  i)
            {
                if(du[i]%2!=0)
                tot  ;
            }
            if(tot==0||tot==2) printf("Yesn");
            else printf("Non");
        }
    }
    return 0;
}

 

zyc从小就比较喜欢玩一些小游戏,当中就回顾画一笔画,他想请你帮她写叁个程序,判定贰个图是或不是能够用一笔画下去。

规定,全体的边都只可以画一次,无法再度画。

  • 输入

先是行唯有多少个正整数N(N<=10)表示测量检验数据的组数。每组测量检验数据的率先行有八个正整数P,Q(P<=1000,Q<=3000),分别表示这些画中有个别许个终端和多少条连线。(点的编号从1到P)随后的Q行,每行有多个正整数A,B(0<A,B<P),表示编号为A和B的两点时期有连线。

  • 输出

若是存在符合条件的连线,则输出"Yes",假如不设有符合条件的连线,输出"No"。

本文由bg游戏资讯发布于单机闯关小游戏,转载请注明出处:bg游戏资讯:一笔画问题,图的连通性

关键词: 图论—— 刷题分析 算法 搜索