[LeetCode]Is Graph Bipartite?

判断二分图的问题，所谓二分图，指的是顶点可以分成两个不相交的集合U和V，使得所有的边的两个端点分别位于集合U和V中。也就是说，如果我们把所有边的一个端点图上红色，另一个端点一定可以全涂成蓝色且不会和之前的红色有冲突。我们只需要去验证这一点即可，从任意点开始，假设其涂为红色，那么相邻的所有点都涂为蓝色，蓝色的所有相邻点涂为红色，依次类推，我们用dfs或者bfs即可验证。最后需要注意的是图可能不是connected的，所以对于所有connected component我们都需要验证。时间复杂度O(V + E)，空间复杂度O(V)，代码如下：

dfs：

	class Solution {
	public:
	bool isBipartite(vector<vector<int>>& graph) {
	unordered_map<int, int> colors;
	for(int i = 0; i < graph.size(); ++i)
	{
	if(colors.find(i) == colors.end() && !dfs(graph, colors, i, 0))
	return false;
	}
	return true;
	}
	private:
	bool dfs(vector<vector<int>>& g, unordered_map<int, int>& colors, int i, int color)
	{
	if(colors.find(i) != colors.end())return colors[i] == color;
	colors[i] = color;
	for(const auto& adj : g[i])
	if(!dfs(g, colors, adj, color ^ 1))
	return false;
	return true;
	}
	};

view raw Is Graph Bipartite?_dfs.cpp hosted with ❤ by GitHub

bfs:

	class Solution {
	public:
	bool isBipartite(vector<vector<int>>& graph) {
	unordered_map<int, int> colors;
	queue<int> q;
	for(int i = 0; i < graph.size(); ++i)
	{
	if(colors.find(i) != colors.end())continue;
	q.push(i);
	colors[i] = 0;
	int color = 1;
	while(q.size())
	{
	int len = q.size();
	for(int i = 0; i < len; ++i)
	{
	int node = q.front();
	q.pop();
	for(const auto& adj : graph[node])
	{
	if(colors.find(adj) != colors.end())
	{
	if(colors[adj] != color)return false;
	}
	else
	{
	colors[adj] = color;
	q.push(adj);
	}
	}
	}
	color ^= 1;
	}
	}
	return true;
	}
	};

view raw Is Graph Bipartite?_bfs.cpp hosted with ❤ by GitHub