LeetCode785 判斷二分圖

題目

存在一個無向圖，圖中有 n 個節點。其中每個節點都有一個介于 0 到 n - 1 之間的唯一編号。給你一個二維數組 graph ，其中 graph[u] 是一個節點數組，由節點 u 的鄰接節點組成。形式上，對于 graph[u] 中的每個 v ，都存在一條位于節點 u 和節點 v 之間的無向邊。該無向圖同時具有以下屬性：

• 不存在自環（graph[u] 不包含 u）。
• 不存在平行邊（graph[u] 不包含重複值）。
• 如果 v 在 graph[u] 内，那麼 u 也應該在 graph[v] 内（該圖是無向圖）
• 這個圖可能不是連通圖，也就是說兩個節點 u 和 v 之間可能不存在一條連通彼此的路徑。

二分圖定義：如果能将一個圖的節點集合分割成兩個獨立的子集 A 和 B ，并使圖中的每一條邊的兩個節點一個來自 A 集合，一個來自 B 集合，就将這個圖稱為 二分圖 。

如果圖是二分圖，傳回 true ；否則，傳回 false 。

示例 1：不是一個二分圖

示例二：是一個二分圖

解題思路

這是一道判斷是否是二分圖的題目，類似于圖着色，可以抽象成能不能将圖中的每條邊的兩個節點塗上不同的顔色。關于二分圖的知識可以看我的另一篇部落格圖結構專欄——判斷二分圖。這道題可以用dfs和bfs兩種方法解決。

2.1 深度優先周遊

vector<int> visited;
	bool ok = true;
	void dfs(vector<vector<int>>& graph, int thisnode, int lastnode)
	{
		if (lastnode == -1)
		{

		}
		else
		{
			if (visited[thisnode] == -1)//這個節點還未通路
			{
				visited[thisnode] = visited[lastnode] ^ 1;
			}
			else//這個節點通路過
			{
				if (visited[thisnode] ^ 1 != visited[lastnode])
				{
					ok = false;
				}
				return;
			}
		}
		for (int i = 0; i < graph[thisnode].size(); i++)
		{
			dfs(graph, graph[thisnode][i], thisnode);
		}
	}
	//參數graph：graph[i]是一個容器，裝有與節點i相連的節點
	bool isBipartite(vector<vector<int>>& graph) {
		visited.resize(graph.size(), -1);
		for (int i = 0; i < graph.size(); i++)
		{
			if (visited[i] == -1)
			{
				visited[i] = 0;
				dfs(graph, i, -1);
			}
		}
		return ok;
	}
           

2.2廣度優先周遊

class Solution {
public:
	vector<int> visited;

	bool isBipartite(vector<vector<int>>& graph) {
		visited.resize(graph.size(), -1);
		queue<int> q;
		for (int i = 0; i < graph.size(); i++)
		{
			if (visited[i] == -1)
			{
				visited[i] = 0;
				q.push(i);
				while (!q.empty())
				{
					int thisnode = q.front();
					q.pop();
					for (int j = 0; j < graph[thisnode].size(); j++)
					{
						if (visited[graph[thisnode][j]] != -1)
						{
							if (visited[graph[thisnode][j]] == visited[thisnode])
								return false;
						}
						else
						{
							visited[graph[thisnode][j]] = visited[thisnode] ^ 1;
							q.push(graph[thisnode][j]);
						}
					}
				}
			}
		}
		return true;
	}
};