图的遍历题目题解

精神病科黄主任

发表于 2020-05-20 13:05:05

题目描述小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍展开全文

Kur1su

发表于 2020-05-26 16:32:18

Description 小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条展开全文

shyyhs

发表于 2021-01-13 15:27:59

前言: 这是一个很不错的思维题! 思路: 这个题就是要让我们来证明一幅图必须有奇数环,才能使得全图被遍历(假如按2步走的话).首先我们对于一棵树来说,我们知道假如我们不走到叶子节点再还回肯定是没有意义的,但是其实我们走到叶子节点再还回也是没有意义的.比方说我们现在有两条链,奇数链和偶数链.奇数链:1 展开全文

19_hanhan

发表于 2020-05-21 00:19:13

题目题目描述：小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你展开全文

JQK2020

发表于 2020-05-25 15:57:38

题目描述小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍展开全文

与人无语

发表于 2020-05-27 17:40:27

对于这一题，一个图如果能被跳两步走完首先要图是联通的即把连通块都连起来 ans=连通块数-1；在然后，如果这个图有奇数环的话我们走两个循环就可以把图都走到如果没有的话就加一条边形成奇数环 ans+=flag;答案就出来了 #include<bits/stdc++.h> 展开全文

苟且的狮子

发表于 2020-07-15 22:41:03

bfs\dfs 题意：链接：https://ac.nowcoder.com/acm/problem/52275来源：牛客网小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方展开全文

gudazifu

发表于 2020-05-25 22:25:19

链接：https://ac.nowcoder.com/acm/problem/52275题目描述小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每展开全文

Canan

发表于 2020-05-20 14:11:36

https://ac.nowcoder.com/acm/problem/52275 题意：需要加多少条边才能使从1开始遍历整张图？分析：先从简单的问题进行考虑，假设每次都只能走1步，那么需要加多少条边才能遍历完呢，显然要把全部点都连通起来，因此需要加的边数就是（连通块的数量-1）条边。如果每次只能展开全文

wxyww

发表于 2020-05-20 14:46:12

solution 我们从1号点开始染色，标记为0的点表示可以从1号点走偶数步到达，标记为1的点表示可以从1号点走奇数步到达。最后就是想要所有点都可以标记为0。如果存在一个奇环，那么这个环上的点既可以标记为1，也可以标记为0，所以所有与这个奇环相连的点都可以标记为0和1。所以我们只要保证最终连接成一展开全文

相关比赛

等你来战