Leetcode - Is Graph Bipartite?

violet posted @ 5 年前 in 算法 with tags Algorithm DFS Golang Graph , 353 阅读

https://leetcode.com/problems/is-graph-bipartite/

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

func isBipartite(graph [][]int) bool {
    n := len(graph)
    group := make([]int, n)
    for i := 0; i < n; i++ {
        if group[i] == 0 && !dfs(graph, &group, i, 1) {
            return false
        }
    }
    return true
}
 
func dfs(graph [][]int, group *[]int, index, g int) bool {
    if (*group)[index] != 0 {
        return (*group)[index] == g
    }
    (*group)[index] = g
    for _, i := range graph[index] {
        if !dfs(graph, group, i, 0 - g) {
            return false
        }
    }
    return true
}