886

1 files changed, 64 insertions, 28 deletions

diff --git a/886/main.go b/886/main.go
index 901bf50..d06b3b8 100644
--- a/886/main.go
+++ b/886/main.go
@@ -2,41 +2,77 @@ package main
 
 import "fmt"
 
-func possibleBipartition(N int, dislikes [][]int) bool {
-	color := make(map[int]bool, N)
-	visited := make(map[int]bool, N)
-	adjList := make(map[int][]int, N)
-
-	for _, d := range dislikes {
-		a := d[0]
-		b := d[1]
-		adjList[a] = append(adjList[a], b)
-		adjList[b] = append(adjList[b], a)
+// func possibleBipartition(N int, dislikes [][]int) bool {
+// 	color := make(map[int]bool, N)
+// 	visited := make(map[int]bool, N)
+// 	adjList := make(map[int][]int, N)
+
+// 	for _, d := range dislikes {
+// 		a := d[0]
+// 		b := d[1]
+// 		adjList[a] = append(adjList[a], b)
+// 		adjList[b] = append(adjList[b], a)
+// 	}
+
+// 	for i := 1; i <= N; i++ {
+// 		if !visited[i] {
+// 			visited[i] = true
+// 			res := isBiparitionDfs(i, adjList, visited, color)
+// 			if !res {
+// 				return false
+// 			}
+// 		}
+// 	}
+
+// 	return true
+// }
+
+// func isBiparitionDfs(cur int, adjList map[int][]int, visited map[int]bool, color map[int]bool) bool {
+// 	for _, next := range adjList[cur] {
+// 		if !visited[next] {
+// 			visited[next] = true
+// 			color[next] = !color[cur]
+// 			res := isBiparitionDfs(next, adjList, visited, color)
+// 			if !res {
+// 				return false
+// 			}
+// 		} else if color[cur] == color[next] {
+// 			return false
+// 		}
+// 	}
+// 	return true
+// }
+
+// red: 1; green: -1
+func possibleBipartition(n int, dislikes [][]int) bool {
+	edges := make([][]int, n+1)
+	for _, dislike := range dislikes {
+		u, v := dislike[0], dislike[1]
+		edges[u] = append(edges[u], v)
+		edges[v] = append(edges[v], u)
 	}
 
-	for i := 1; i <= N; i++ {
-		if !visited[i] {
-			visited[i] = true
-			res := isBiparitionDfs(i, adjList, visited, color)
-			if !res {
+	color := make([]int, n+1)
+
+	var dfs func(u, c int) bool
+	dfs = func(u, c int) bool {
+		if color[u] != 0 {
+			return color[u] == c
+		}
+
+		//fmt.Printf("node: %d will mark color: %d\n", u, c)
+		color[u] = c
+		for _, v := range edges[u] {
+			if !dfs(v, -c) {
 				return false
 			}
 		}
-	}
 
-	return true
-}
+		return true
+	}
 
-func isBiparitionDfs(cur int, adjList map[int][]int, visited map[int]bool, color map[int]bool) bool {
-	for _, next := range adjList[cur] {
-		if !visited[next] {
-			visited[next] = true
-			color[next] = !color[cur]
-			res := isBiparitionDfs(next, adjList, visited, color)
-			if !res {
-				return false
-			}
-		} else if color[cur] == color[next] {
+	for u := 1; u <= n; u++ {
+		if color[u] == 0 && !dfs(u, 1) {
 			return false
 		}
 	}