奇环:节点数为奇数的环
二分图性质:一定没有奇环 反之则说明不是二分图
基本思路:
bfs统计深度 检测到走过的点则计算深度相差数值,如果是奇数则说明是奇环
注意差值需要加1,原理就和1到3有三个点而3-1=2一样
代码:
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 100010;
struct Node {
vector<int> next;
} nodes[N];
int dist[N];
bool st[N];
bool bfs(int t) {
dist[t] = 0;
st[t] = true;
queue<int> q;
q.push(t);
int now = 0;
while(!q.empty()) {
int size = q.size();
for(int i = 0;i < size;i ++) {
int h = q.front();
q.pop();
for(int x : nodes[h].next) {
if(st[x]) {
if((now - dist[x]+1)%2==1) {
puts("No");
return true;
}
} else {
q.push(x);
st[x] = true;
dist[x] = now + 1;
}
}
}
now ++;
}
return false;
}
int main() {
int m, n;
cin >> n >> m;
memset(st, 0, sizeof st);
memset(dist, -1, sizeof dist);
for(int i = 0;i < m;i ++) {
int a, b;
cin >> a >> b;
nodes[a].next.push_back(b);
nodes[b].next.push_back(a);
}
for(int i = 1;i <= n;i ++)
if(dist[i] == -1)
if(bfs(i))
return 0;
puts("Yes");
return 0;
}
特殊点分析:自环,重边和双向边问题
自环:假设自环的节点为x
, 深度dist
为y
,当前走到的深度now
为y+1
, 即dist[x]=y
。
这时计算深度差值now - dist[x] + 1
= 2, 不会被当成奇环
重边:因为是检测到访问过的点就算作环,所以重边需要额外分析,重边其实和自环类似。假设x
到y
有两条边,第一次从x
走到y
时,dist[y]
会更新为now+1
, 然后后面再遇到y时 深度是没变的 因为都是x
延伸出来的点 计算深度差值会是now - (now + 1) + 1
= 0 不会作为奇环
双向变:因为是无向图,所以需要额外分析双向边造成的环,假设有一条边x
到y
。那么从x
走到y
后还会有一条边指回x
。这时候dist[x]
是now-1
, 然后深度差值会是now-(now-1)+1
=2,也不会被作为奇环
问题:
还有一个额外的问题是我的bfs是搜索了所有可以搜索的点,也就是我允许了多个二分图存在的可能性,但是题目没说清楚。如果只有一个二分图,其实随便搜索一个图中的点就够了 但是我试了会卡在17/19(截止我写这篇题解的日期)。并且那一组数据太大了 不太好分析。我只能猜测是多组二分图存在吧。反正假设允许多组就AC了,也不是什么大问题 最主要的是深度差统计环大小的思路 还有那几个特殊点的分析。