【模板】二分图结构Ⅰ‑A || 染色判定DFS时间限制5秒空间限制1024M知识点第四范式、贪心、算法工程师、2019、图描述对于给定的由nnn个顶点、mmm条边构成的无向连通图判定其是否为二分图。名词解释二分图可将顶点集合划分为两个独立集且所有边均连接不同集合的图。输入描述第一行输入两个整数n,m(1≤n,m≤3×105)n,m (1 \le n,m \le 3 \times 10^5)n,m(1≤n,m≤3×105)代表顶点数量、边数量。此后mmm行第iii行输入两个整数uiu_iui​和vi (1≤ui,vi≤n; ui≠vi)v_i\ (1 \le u_i,v_i \le n;\ u_i \neq v_i)vi​(1≤ui​,vi​≤n;ui​vi​)表示图上第iii条边双向连接顶点uiu_iui​和viv_ivi​。图可能存在重边。不存在自环、保证连通。输出描述如果给定的图不是一张二分图输出NO否则输出YES。示例1输入5 6 1 2 2 3 3 4 4 1 4 5 5 2输出YES说明在这个样例中把顶点1,3,51,3,51,3,5点染色为白2,42,42,4点染色为黑即可满足二分图要求所以这个图是二分图。示例2输入5 4 1 2 2 3 3 1 4 5输出NO说明备注本题已于下方时间节点更新请注意题解时效性2025‑07‑07 优化题面文本与格式2025‑11‑28 第一组样例mmm与实际边数不符修正。模板题为便于测试将时间限制扩充至 5s空间限制扩充至 1024MB。2025‑12‑05 对题面与数据进行了微调以匹配整套模板题n,mn,mn,m从10510^5105增加到3×1053\times 10^53×105输出修改为全大写的YES和NO去除了题面背景增加了重边数据。解题思路本题是二分图判定的模板题要求判断一个无向连通图能否将顶点划分为两个集合使得每条边都连接不同集合的顶点。这等价于判断图是否能被二染色即相邻顶点颜色不同。采用 BFS 染色法在遍历过程中为每个顶点分配颜色1 或 2若发现相邻顶点颜色冲突则不是二分图。1. 问题等价转化二分图判定一个无向图是二分图当且仅当它能用两种颜色对顶点染色使得任意一条边的两个端点颜色不同。染色冲突检测从任意顶点出发将其染为颜色 1其所有邻居染为颜色 2邻居的邻居再染回颜色 1依此类推。若在遍历过程中遇到某个已染色顶点其颜色与将要染的颜色相同则说明存在奇环图不是二分图否则是二分图。连通性说明题目保证图连通因此从任意一个顶点出发即可遍历所有顶点。代码仍遍历所有未染色顶点以兼容非连通图。2. 算法实现BFS 染色建图使用邻接表adj存储无向边。代码中add函数内部已经添加了双向边但主函数又调用了两次add导致每条边被重复存储四次不影响正确性只会增加一点常数。初始化颜色数组col[i]表示顶点i的颜色初始为 0未染色1 和 2 分别代表两种颜色。BFS 染色对每个未染色顶点i调用bfs(i, col, adj)。在 BFS 中将起点染为 1。遍历当前顶点的所有邻居v若v未染色则将其染为3 - col[u]即 1 变 22 变 1并入队。若v已染色且颜色与当前顶点相同则返回false表示不是二分图。结果输出若所有连通分量都成功染色输出YES否则输出NO。3. 复杂度分析时间复杂度每个顶点和每条边均被访问常数次尽管代码中边被重复存储但整体仍为O(nm)O(nm)O(nm)n,m≤3×105n,m \le 3\times 10^5n,m≤3×105在 5 秒时限内完全可行。空间复杂度邻接表O(nm)O(nm)O(nm)颜色数组O(n)O(n)O(n)。总结利用 BFS 进行二染色实时检测相邻顶点颜色是否冲突即可在线性时间内判定二分图。该方法通用且实现简单是二分图判定的标准模板。代码简要说明add函数向邻接表中添加一条无向边实际上添加了两个方向。bfs函数从起点开始 BFS使用颜色数组col进行交替染色发现冲突立即返回false。主函数读入顶点数nnn和边数mmm构建邻接表。遍历所有顶点对未染色顶点调用bfs。若任一 BFS 返回false输出NO并提前结束否则输出YES。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidadd(ll u,ll v,vectorvectorlladj){adj[u].push_back(v);adj[v].push_back(u);}boolbfs(ll st,vectorllcol,vectorvectorlladj){queuellq;q.push(st);col[st]1;while(!q.empty()){ll uq.front();q.pop();for(ll v:adj[u]){if(col[v]0){col[v]3-col[u];q.push(v);}else{if(col[v]col[u])returnfalse;}}}returntrue;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cinnm;vectorvectorlladj(n1);while(m--){ll u,v;cinuv;add(u,v,adj);add(v,u,adj);}vectorllcol(n1,0);for(ll i1;in;i){if(col[i]0){if(!bfs(i,col,adj)){coutNOendl;return0;}}}coutYESendl;return0;}