1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

  • 二分图充要条件:图中不存在奇环。
  • 经典做法:对每个连通分量做 BFS/DFS 染色。起点染 0,邻点染 1,继续扩展;若遇到与已染相邻点颜色相同,则不是二分图。
  • 图可能不连通,需从所有未染色点发起遍历;允许孤点。

算法步骤

  • 建邻接表(1..n)。

P3385.第1题-二分图

    1000ms Tried: 124 Accepted: 37 Difficulty: 5 所属公司 : 虾皮
    算法与标签>BFS

题目描述

给定一个无向图,判断该图是否为二分图。若可将顶点集合划分为两个不相交的子集,使得任意一条边的两个端点分属不同子集,则该图为二分图。

输入格式

  • 第一行包含两个整数 n m,表示图的顶点数与边数(顶点从 1 到 n 编号)。
  • 接下来 m 行,每行两个整数 u v,表示一条无向边 (u, v)。

输出格式

  • 对于每组数据,若图是二分图输出 Yes,否则输出 No。

样例输入

4 4
1 2
2 3
3 4
4 1

样例输出

Yes

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 2, 49ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?