---

二分图等价定义：不含奇数条边的环。

染色法：

（1）dfs，链式前向星

#include<iostream>
using namespace std;
const int N = 1010;
int h[N], e[N], next_pos[N], n, m, idx;
int color[N];
void add(int a, int b){
	e[++idx] = b;
	next_pos[idx] = h[a];
	h[a] = idx;
}

bool dfs(int u, int c){//将u节点染成c颜色
	color[u] = c;
	for (int i = h[u]; i; i = next_pos[i]){
		int j = e[i];
		if (color[j] == -1){
			if (!dfs(j, !c)){ return false; }
		}
		else if (color[j] == c){ return false; }
	}
	return true;
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	memset(color, -1, sizeof color);
	bool flag = true;
	for (int i = 1; i <= n; i++){
		if (color[i] == -1){
			if (!dfs(i, 0)){
				flag = false;
				break;
			}
		}
	}
	if (flag){
		cout << "yes" << endl;
	}
	else{
		cout << "no" << endl;
	}

	return 0;
}

bfs：vector<int>g[N];实现图链接存储为例

...