图的遍历(二分图)

图的遍历

https://ac.nowcoder.com/acm/problem/52275


题目:

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


做法:

两步走不难往二分图上想。如果一幅图是二分图,将图分成2个集合。从1出发只能走到1所在集合中的点。而只要该图不是二分图,必定有一条边连接同一个集合中的2个点,进而可以从一个集合走到另一个集合,也就能走完所有点。
所以这题做法是:先求出所有联通块。联通块数量-1条边是必须加的。然后看一下每个联通块是否有非二分图。若有就不需另加边。否则加一条边。


代码:

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, m, col[N], extra;
vector<int> g[N];
void dfs(int u, int c){
    col[u] = c;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (!col[v]) dfs(v, 3-c);
        if (col[v] == col[u]) extra = 0;
    }
}
int main(void){ 
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    extra = 1;
    int cnt = -1;
    for (int i = 1; i <= n; ++i){
        if (!col[i]){
            dfs(i, 1), cnt++;
        }
    }
    cout << cnt+extra << endl;
    return 0;
}
全部评论

相关推荐

02-05 08:49
已编辑
武汉大学 Java
野猪不是猪🐗:36k和36k之间亦有差距,ms的36k和pdd的36k不是一个概念
点赞 评论 收藏
分享
双飞二本嵌入式求拷打我是在&nbsp;BOSS&nbsp;上投递的简历,好多都没人回复,这是开场白和简历求大神帮忙看看。您好!我是2025届应届生,最快可在一周内上岗,能够实习六个月以上,并接受加班。以下是我的核心优势和相关经验:1.&nbsp;嵌入式开发能力:&nbsp;&nbsp;&nbsp;熟练掌握STM32系列单片机及其外设(如GPIO、定时器、ADC、DAC、I2C、SPI、UART等),能够独立完成硬件驱动开发和调试。&nbsp;&nbsp;熟悉FreeRTOS实时操作系统,具备多任务调度和资源管理经验。&nbsp;&nbsp;熟悉LVGL图形库开发,能够实现嵌入式设备的图形界面设计。2.&nbsp;硬件设计能力:&nbsp;&nbsp;&nbsp;具备PCB设计经验,曾为2023年工创赛物流搬运赛道设计小车主板,带领团队获得国家级银奖。&nbsp;&nbsp;&nbsp;熟悉硬件原理图分析,能够快速理解并调试硬件电路。3.&nbsp;机器人开发与竞赛经验:&nbsp;&nbsp;&nbsp;在全国大学生智能车竞赛、ROS机器人竞赛中多次获得国家级奖项,具备丰富的机器人开发经验。&nbsp;&nbsp;&nbsp;熟悉Linux环境,对ROS和ROS&nbsp;2有一定了解,能够进行机器人系统的开发与调试。4.&nbsp;编程能力:&nbsp;&nbsp;&nbsp;熟悉C/C++,熟悉Python,能够高效完成嵌入式开发和算法实现。&nbsp;&nbsp;&nbsp;具备良好的代码规范和文档编写能力。5.&nbsp;团队协作与领导能力:&nbsp;&nbsp;&nbsp;在多个项目中担任核心开发或团队负责人,具备良好的沟通能力和团队协作精神。&nbsp;&nbsp;&nbsp;在工创赛中带领团队完成项目规划、任务分配和技术攻关,展现了较强的领导力。我对嵌入式开发、机器人技术和智能硬件充满热情,期待加入贵公司,与团队共同成长,为公司创造价值!如果有合适的岗位,欢迎随时联系我,期待进一步沟通!
沉淀一会:嵌入式就是狗屎
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务