文章

25

粉丝

0

获赞

0

访问

68535

头像
二分图判定
经验总结
发布于2020年4月15日 23:42
阅读数 2384

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

染色法:

(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];实现图链接存储为例

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N = 1010;
vector<int> g[N];
int n, m, color[N];
bool bfs(int father){
	queue<pair<int,int>>q;
	color[1] = 2;
	q.push({ 1, father });
	while (q.size()){
		pair<int,int> t = q.front();
		q.pop();
		for (int i = 0; i < g[t.first].size(); i++){
			if (g[t.first][i] == t.first){ continue; }
			if (color[g[t.first][i]] == color[t.first]){
				return  false;
			}
			else if (color[g[t.first][i]]==-1){
				color[g[t.first][i]] = -color[t.first];
				q.push({ g[t.first][i], t.first }); 
			}
		}
	}
	return true;
}
int main(){
	cin >> n >> m;
	memset(color, -1, sizeof color);
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	bool flag = true;
	for (int i = 1; i <= n; i++){
		if (color[i] == -1){
			if (!bfs(i)){
				flag = false;
				break;
			}
		}
	}
	for (int i = 1; i <= n; i++){
		cout << color[i] << " ";
	}
	cout << endl;
	if (flag){
		cout << "yes" << endl;
	}
	else{
		cout << "no" << endl;
	}

	return  0;
}

 



登录后发布评论

暂无评论,来抢沙发