信息学奥赛一本通 1341:【例题】一笔画问题

这篇具有很好参考价值的文章主要介绍了信息学奥赛一本通 1341:【例题】一笔画问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【题目链接】

ybt 1341:【例题】一笔画问题

【题目考点】

1. 图论:欧拉回路

求解欧拉回路使用Hierholzer算法
复杂度: O ( V + E ) O(V+E) O(V+E)

【解题思路】

  • 无向图有欧拉回路的条件:所有顶点的度都是偶数。
  • 无向图有欧拉路径的条件:有两个顶点的度是奇数,其余顶点的度都是偶数。

该题默认一定有欧拉路径或欧拉回路。
遍历选择起始顶点,如果v的度为奇数,那么选择该顶点为起始顶点。否则起始顶点默认为1号顶点。
使用Hierholzer算法可以在 O ( V + E ) O(V+E) O(V+E)的时间复杂度内求出欧拉回路。
顶点数n最大为100,可以使用邻接矩阵或邻接表解决。文章来源地址https://www.toymoban.com/news/detail-639804.html

【题解代码】

解法1:邻接矩阵
#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, edge[N][N], deg[N];//n:顶点数 m:边数 deg[i]:顶点i的度 
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{
    for(int v = 1; v <= n; ++v)
    {
        if(edge[u][v])
        {
            edge[u][v] = edge[v][u] = 0;
            dfs(v);        
        }
    }
    stk.push(u);
}
int main()
{
    int st = 1, f, t;//st:起点 
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        edge[f][t] = edge[t][f] = 1;
        deg[f]++, deg[t]++;
    }
    for(int v = 1; v <= n; ++v)//如果找到奇数度顶点,就从奇数度顶点出发,否则从1出发 
    {
        if(deg[v] % 2 == 1)
        {
            st = v;
            break;
        }
    }
    dfs(st);
    while(stk.empty() == false)
    {
        cout << stk.top() << ' ';
        stk.pop();
    }
    return 0;
}
解法2:邻接表
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define M 2005
struct Node
{
	int v, e;//v:顶点编号 e:边的编号 
	Node(){}
	Node(int a, int b):v(a), e(b){}
};
int n, m, deg[N], beg[N];//n:顶点数 m:边数 deg[i]:顶点i的度 beg[i]:顶点i的邻接点从edge[beg[i]]开始算起,前面的相当于删掉了。 
vector<Node> edge[N];
bool vis[M];
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{
	for(int &i = beg[u]; i < edge[u].size(); ++i)//i是beg[u]的引用,++i相当于++beg[u],这样在下一次访问顶点u的邻接点时,只需要从下标beg[u]开始看起,前面的当做已经被删掉了
	{
		int v = edge[u][i].v, e = edge[u][i].e;
		if(vis[e] == false)
		{
			vis[e] = true;
			dfs(v);
		}
	}
    stk.push(u);
}
int main()
{
    int st = 1, f, t;//st:起点 
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        edge[f].push_back(Node(t, i));
        edge[t].push_back(Node(f, i));
        deg[f]++, deg[t]++;
    }
    for(int v = 1; v <= n; ++v)//如果找到奇数度顶点,就从奇数度顶点出发,否则从1出发 
    {
        if(deg[v] % 2 == 1)
        {
            st = v;
            break;
        }
    }
    dfs(st);
    while(stk.empty() == false)
    {
        cout << stk.top() << ' ';
        stk.pop();
    }
    return 0;
}

到了这里,关于信息学奥赛一本通 1341:【例题】一笔画问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 信息学奥赛一本通习题答案(一)

    最近在给小学生做C++的入门培训,用的教程是信息学奥赛一本通,刷题网址为http://ybt.ssoier.cn:8088/index.php 现将部分习题的答案放在博客上,希望能给其他有需要的人带来帮助 篇幅有限,所以从分支结构开始,所有代码都可以正确提交,鉴于本人能力有限以及教学需要,部分代

    2024年02月16日
    浏览(38)
  • 信息学奥赛一本通(1398:短信计费)

    1398:短信计费 时间限制: 1000 ms         内存限制: 65536 KB 提交数: 22811     通过数: 10561 【题目描述】 用手机发短信,一条短信资费为0.1元,但限定一条短信的内容在70个字以内(包括70个字)。如果你一次所发送的短信超过了70个字,则会按照每70个字一条短信的限制把它分

    2023年04月08日
    浏览(75)
  • 信息学奥赛一本通 1376:信使(msner)

    ybt 1376:信使(msner) 1. 图论:最短路径 每个哨所是一个顶点,哨所与哨所之间的通信线路为边,两哨所间通讯花费的时间为边的权值。 记第一个哨所为顶点s,信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径,每条传送路径有一个花费的时间,自然要选择花费时

    2024年02月14日
    浏览(74)
  • 信息学奥赛一本通 1384:珍珠(bead)

    ybt 1384:珍珠(bead) 1. 图论:floyd 求传递闭包 传递闭包:二维数组e, e[i][j] 表示顶点i到顶点j是否有路径。 这是个有向图。每颗珍珠是一个顶点,初始情况下,如果i比j重,那么i到j有一条弧。 设布尔类型数组e,为该图的传递闭包,即 e[i][j] 表示i是否比j重。 先输入已知的相

    2024年01月24日
    浏览(39)
  • 信息学奥赛一本通:1119:矩阵交换行

    【题目描述】 给定一个5×5的矩阵(数学上,一个r×c的矩阵是一个由r行c列元素排列成的矩形阵列),将第n行和第m行交换,输出交换后的结果。 【输入】 输入共6行,前5行为矩阵的每一行元素,元素与元素之间以一个空格分开。 第6行包含两个整数m、n,以一个空格分开(1≤m,

    2024年02月22日
    浏览(38)
  • 信息学奥赛一本通 1380:分糖果(candy)

    ybt 1380:分糖果(candy) 可以认为小朋友间关系的最大数量为 1 0 5 10^5 1 0 5 1. 图论:广搜 2. 图论:最短路径 每个小朋友是一个顶点,朋友间的关系是边,糖果从每个人传到另一个人都是1秒钟的时间,因而该图是无向无权图。 假设一位小朋友A接收糖果的时刻是t,那么与该小朋友

    2023年04月08日
    浏览(71)
  • 信息学奥赛一本通 1352 【例4-13】奖金

    ybt 1352 【例4-13】奖金 1. 图论:拓扑排序 解法1:拓扑排序 每个人是一个顶点。 如果a奖金比b高,应该先确定b的奖金数,再确定a的奖金。 因此可以这样定义边:如果b的奖金比a高,那么存在有向边a, b。 设数组money,顶点i的奖金为 money[i] 。 图中入度为0的顶点的奖金为100。

    2024年02月16日
    浏览(43)
  • 信息学奥赛一本通(1162:字符串逆序)

    1162:字符串逆序 时间限制: 1000 ms         内存限制: 65536 KB 提交数: 14027     通过数: 10525 【题目描述】 输入一串以‘!’结束的字符,按逆序输出。 【输入】 如题述。 【输出】 如题述。 【输入样例】 【输出样例】 【分析】         逆序输出字符串,本身不难,可以

    2023年04月17日
    浏览(38)
  • 信息学奥赛一本通 1386:打击犯罪(black)

    ybt 1386:打击犯罪(black) 1. 并查集 这是个无向图。每个犯罪团伙是一个顶点,犯罪团伙之间的联系是边,每个犯罪集团是一个连通分量。 以下描述中,连通分量就对应了并查集中集合的概念。 “犯罪团伙的危险程度”是连通分量中的顶点数。“最大的犯罪团伙的危险程度不超

    2024年02月10日
    浏览(40)
  • 信息学奥赛一本通 1374:铲雪车(snow)

    ybt 1374:铲雪车(snow) 洛谷 UVA10203 Snow Clearing 注:原题输入要求更复杂,本文代码无法通过。 1. 图论:欧拉回路 2. 两点间距离公式 d i s = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 dis = sqrt{(x_1-x_2)^2+(y_1-y_2)^2} d i s = ( x 1 ​ − x 2 ​ ) 2 + ( y 1 ​ − y 2 ​ ) 2 ​ 所有的道路都是双车道,对于一

    2024年02月11日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包